Rekursion ist eine Programmiertechnik, bei der sich eine Funktion wiederholt aufruft, bis eine Beendigungsbedingung erfüllt ist. Einige der Beispiele, bei denen die Rekursion verwendet wird, sind: Berechnung von Fibonacci Reihen, Fakultät usw. Das Problem bei ihnen ist jedoch, dass im Rekursionsbaum die Möglichkeit besteht, dass das bereits gelöste Teilproblem erneut gelöst wird, was hinzugefügt wird zu einem Overhead.

Das Auswendiglernen ist eine Technik zum Aufzeichnen der Zwischenergebnisse, um wiederholte Berechnungen zu vermeiden und die Programme zu beschleunigen. Es kann verwendet werden, um die Programme zu optimieren, die Rekursion verwenden. In Python kann das Auswendiglernen mithilfe von Funktionsdekoratoren erfolgen.

Nehmen wir das Beispiel der Berechnung der Fakultät einer Zahl. Das folgende einfache Programm verwendet Rekursion, um das Problem zu lösen:

def facto(num): 
    if num == 1: 
        return 1
    else: 
        return num * facto(num-1) 
          
  
print(facto(5)) 

Das obige Programm kann durch Auswendiglernen mit Dekoratoren optimiert werden .

  
def memoize_factorial(f): 
    memory = {} 
  
    
    
    def inner(num): 
        if num not in memory:          
            memory[num] = f(num) 
        return memory[num] 
  
    return inner 
      
@memoize_factorial
def facto(num): 
    if num == 1: 
        return 1
    else: 
        return num * facto(num-1) 
  
print(facto(5)) 

Erläuterung:
1. Eine Funktion namens memoize_factoria l wurde definiert. Der Hauptzweck besteht darin, die Zwischenergebnisse in der Variablen namens Speicher zu speichern.
2. Die zweite Funktion namens facto ist die Funktion zur Berechnung der Fakultät. Es wurde von einem Dekorateur (der Funktion memoize_factorial) mit Anmerkungen versehen. Das Fakto hat aufgrund des Konzepts der Schließungen Zugriff auf die Speichervariable. Die Anmerkung entspricht dem Schreiben,

facto = memoize_factorial (facto)

3. Wenn facto (5) aufgerufen wird, finden die rekursiven Operationen zusätzlich zur Speicherung von Zwischenergebnissen statt. Jedes Mal, wenn eine Berechnung durchgeführt werden muss, wird überprüft, ob das Ergebnis im Speicher verfügbar ist . Wenn ja, wird es verwendet, andernfalls wird der Wert berechnet und im Speicher gespeichert .
4. Wir können überprüfen, ob die Memoisierung tatsächlich funktioniert. Weitere Informationen finden Sie in der Ausgabe dieses Programms.