Memoización usando decoradores en Python

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:
 

# 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 .
 

# 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.