La recursividad es una técnica de programación en la que una función se llama a sí misma repetidamente hasta que se cumple una condición de terminación. Algunos de los ejemplos en los que se usa la recursividad son el cálculo de series de Fibonacci , factorial, etc. Pero el problema con ellos es que en el árbol de recursividad, puede haber posibilidades de que el subproblema que ya se resolvió se resuelva nuevamente, lo que agrega a la sobrecarga.
La memorización es una técnica de registro de los resultados intermedios para que pueda usarse para evitar cálculos repetidos y acelerar los programas. Se puede usar para optimizar los programas que usan recursividad. En Python, la memorización se puede realizar con la ayuda de decoradores de funciones.
Tomemos el ejemplo de calcular el factorial de un número. El programa simple a continuación usa la recursividad para resolver el problema:
Python3
# Simple recursive program to find factorial def facto(num): if num == 1: return 1 else: return num * facto(num-1) print(facto(5)) print(facto(5)) # again performing same calculation
120 120
El programa anterior se puede optimizar mediante la memorización utilizando decoradores .
Python3
# Factorial program with memoization using # decorators. # A decorator function for function 'f' passed # as parameter memory = {} def memoize_factorial(f): # This inner function has access to memory # and 'f' def inner(num): if num not in memory: memory[num] = f(num) print('result saved in memory') else: print('returning result from saved memory') return memory[num] return inner @memoize_factorial def facto(num): if num == 1: return 1 else: return num * facto(num-1) print(facto(5)) print(facto(5)) # directly coming from saved memory
result saved in memory result saved in memory result saved in memory result saved in memory result saved in memory 120 returning result from saved memory 120
Explicación:
1. Se ha definido una función llamada memoize_factoria l. Su objetivo principal es almacenar los resultados intermedios en la variable llamada memoria.
2. La segunda función llamada facto es la función para calcular el factorial. Ha sido anotado por un decorador (la función memoize_factorial). El facto tiene acceso a la memoria variable como resultado del concepto de cierres. La anotación equivale a escribir,
facto = memoize_factorial(facto)
3. Cuando se llama a facto(5), las operaciones recursivas tienen lugar además del almacenamiento de resultados intermedios. Cada vez que se necesita hacer un cálculo, se verifica si el resultado está disponible en la memoria . Si es así, entonces se usa, de lo contrario, el valor se calcula y se almacena en la memoria .
4. Podemos verificar el hecho de que la memorización realmente funciona, consulte el resultado de este programa.
Publicación traducida automáticamente
Artículo escrito por SamyuktaSHegde y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA