Problema al llamar a un método recursivo memoizado en Python
Estoy siguiendo un curso sobre programación dinámica utilizando recursión y memoización para reducir la complejidad temporal del algoritmo. Me he dado cuenta de que al ejecutar dos ejemplos diferentes serializados en el mismo proceso de Python, los resultados no son los esperados, mostrando algún tipo de memoria entre las llamadas de función. Aquí pego el código:
def can_sum(target_sum, numbers, memo={}):
if target_sum in memo: return memo[target_sum]
if target_sum == 0: return True
if target_sum < 0: return False
for num in numbers:
remainder = target_sum - num
if can_sum(remainder, numbers, memo) == True:
memo[target_sum] = True
return True
memo[target_sum] = False
return False
if name == "main":
print(can_sum(7, [2, 3])) # True
print(can_sum(7, [2, 4])) # False
La salida es:
True
True
cuando en realidad debería ser:
True
False
¿Alguien tiene alguna idea de qué está sucediendo aquí? Si comento la primera llamada, entonces el resultado obtenido para la segunda llamada es el esperado.
Muchas gracias de antemano.
davy.ai
Parece que el problema está relacionado con el uso de un objeto mutable (diccionario) como valor predeterminado para el parámetro memo. En Python, los valores de los parámetros predeterminados se evalúan solo una vez cuando se define la función, y no cada vez que se llama a la función. Esto significa que se reutiliza el mismo diccionario para diferentes llamadas a la función, lo que provoca un comportamiento inesperado.
Para solucionar esto, se recomienda utilizar None como el valor predeterminado para memo y luego crear un nuevo diccionario dentro de la función si el parámetro es None. De esta manera, se creará un nuevo diccionario para cada llamada a la función y no habrá ninguna memoria no deseada entre las llamadas a la función.
Aquí hay una versión actualizada del código que debería funcionar correctamente:
¡Espero que esto ayude!