If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Die Effizienz von rekursiven Funktionen verbessern

Rekursion kann ein eleganter Weg sein, um ein Problem zu lösen, und viele Algorithmen eignen sich für rekursive Lösungen. Allerdings können rekursive Algorithmen ineffizient sein, sowohl was die Zeit als auch den Platz angeht. Wir werden hier verschiedene Techniken zur Verbesserung ihrer Effizienz untersuchen.
In der Code-Challenge zur rekursiven Berechnung der Fakultät einer Zahl haben wir dich gebeten, die Funktion mehrfach mit verschiedenen Werten aufzurufen.
Dieser JavaScript-Code ruft zum Beispiel die Funktion factorial() 4 mal auf:
factorial(0);
factorial(2);
factorial(5);
factorial(10);
Betrachten wir alle Aufrufe des Computers wenn er diese 4 Codezeilen ausführt:
CodezeileRekursive AufrufeTotal Aufrufe
factorial(0)1 Aufruf
factorial(2)factorial(1)factorial(0)3 Aufrufe
factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)6 Aufrufe
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)11 Aufrufe
Beachte, dass factorial(10) 11 Funktionsaufrufe machen muss, und 6 davon haben genau die gleichen Argumente und Rückgabewerte wie die vorherigen Funktionsaufrufe, die während factorial(5) gemacht wurden.

Memoisierung der Fakultät

Wir können eine Technik namens Memoization verwenden, um dem Computer bei identischen Funktionsaufrufen Zeit zu sparen. Memoization (eine Form des Cachings) merkt sich das Ergebnis eines Funktionsaufrufs mit bestimmten Eingaben in einer Nachschlagetabelle (dem "Memo") und gibt dieses Ergebnis zurück, wenn die Funktion erneut mit den gleichen Eingaben aufgerufen wird.
Eine Memoisierung der Faktorfunktion könnte so aussehen:
  • Wenn n = 0, gib 1
  • Ansonsten, wenn n im Memo steht, gib den Wert des Memos für n
  • Ansonsten,
    • Berechne (n1)!×n
    • Speichere das Ergebnis im Memo
    • Gib das Ergebnis zurück
Dieser Algorithmus prüft auf den Eingabewert im Memo, bevor er einen potentiell teuren rekursiven Aufruf macht. Das Memo sollte eine Datenstruktur mit effizienten Nachschlagezeiten sein, wie z.B. eine Hashtabelle mit O(1) Lookup-Zeit.
Wenn du die Ausführung des in JavaScript implementierten memoisierten Algorithmus sehen möchtest, schau dir dieses Video an oder führe es aus. Bevor du es dir ansiehst, kannst du dich selbst fordern und den Algorithmus in einer Sprache deiner Wahl implementieren.
Wenn Memoisierung implementiert ist, muss der Computer weniger Gesamtaufrufe für wiederholte Aufrufe von factorial() machen:
CodezeileRekursive AufrufeTotal Aufrufe
factorial(0)1 Aufruf
factorial(2)factorial(1)factorial(0)3 Aufrufe
factorial(5)factorial(4)factorial(3)factorial(2)3 Aufrufe
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)6 Aufrufe
Memoisierung macht einen Kompromiss zwischen Zeit und Platz. Solange das Nachschlagen effizient ist und die Funktion wiederholt aufgerufen wird, kann der Computer Zeit auf Kosten des Speicherplatzes für das Memo sparen.

Memoisierung von Fibonacci

Im Fall der Fakultät profitiert ein Algorithmus nur dann von der Optimierung der Memoisierung, wenn ein Programm die Funktion während seiner Ausführung wiederholt aufruft. In manchen Fällen kann die Memoisierung aber auch bei einem einzigen Aufruf einer rekursiven Funktion Zeit sparen.
Schauen wir uns ein einfaches Beispiel an, den Algorithmus zur Erzeugung von Fibonacci-Zahlen.
Die Fibonacci-Folge ist eine berühmte Zahlenreihe, bei der die nächste Zahl in der Folge die Summe der vorherigen 2 Zahlen ist. Die ersten beiden Zahlen in der Folge sind als 0 und 1 definiert. Danach ist die nächste Zahl 1 (aus 0+1) und die Zahl danach ist 2 (aus 1+1), und so weiter.
Die ersten 10 Fibonacci Zahlen:
0,1,1,2,3,5,8,13,21,34
Eine einfache rekursive Funktion zur Erzeugung der n-ten Fibonacci-Zahl sieht wie folgt aus:
  • Wenn n 0 oder 1 ist, gib n
  • Ansonsten gib fibonacci(n1)+ extfibonacci(n2) zurück
Dieser Algorithmus ist ein Beispiel für eine mehrfache Rekursion, da er sich selbst mehrfach aufruft. Um die mehrfachen Aufrufe, die der Computer macht, zu verstehen, hilft es, die Aufrufe als Baum zu visualisieren.
Wenn n=5, macht der Computer 15 Anrufe:
Khan Academy Video-Wrapper
Recursive Fibonacci Calls (Diagrammed)Video-Transkript ansehen
Beachte die mehrfachen Aufrufe der Fibonacci-Funktion für die Eingabewerte 3, 2, 1 und 0. Je größer die Eingabe wird, desto ineffizienter wird dies. Ein Aufruf von fibonacci(30) führt dazu, dass der Computer fibonacci(2) über eine halbe Million Mal aufruft.
Wir können hier die Memoisierung nutzen, um zu verhindern, dass der Computer eine Fibonacci-Zahl, die er bereits berechnet hat, erneut berechnet.
Die memoisierte Version des rekursiven Fibonacci-Algorithmus sieht wie folgt aus:
  • Wenn n 0 oder 1 ist, gib n zurück
  • Andernfalls, wenn n im Memo steht, gib den Wert des Memos für n zurück
  • Andernfalls,
    • Berechne fibonacci(n1)+fibonacci(n2)
    • Speichere das Ergebnis im Memo
    • Gib das Ergebnis zurück
Wenn du die Ausführung des in JavaScript implementierten memoisierten Algorithmus sehen möchtest, schau dir dieses Video an oder führe das Program aus.
Für n=5 macht der Computer 9 Anrufe:
Khan Academy Video-Wrapper
Memoized Recursive Fibonacci Calls (Diagrammed)Video-Transkript ansehen
Die ursprüngliche Version des Algorithmus benötigte 15 Funktionsaufrufe, so dass die Memoisierung 6 Funktionsaufrufe eliminierte.
Diese Tabelle zeigt die Anzahl der benötigten Aufrufe für n=5 bis zu n=10:
nOriginalMemoisiert
5159
62511
74113
86715
910917
1017719
Die Gesamtzahl der Funktionsaufrufe steigt für den ursprünglichen Algorithmus exponentiell an, für den memoisierten Algorithmus jedoch deutlich langsamer und linear.
Der memoisierte Algorithmus benötigt jedoch mehr Platz; genug für das Memo, um jeden Rückgabewert von n zu speichern.

Bottom-up

Manchmal ist der beste Weg, die Effizienz eines rekursiven Algorithmus zu verbessern, gar keine Rekursion zu verwenden.
Im Fall der Generierung der Fibonacci-Zahlen kann eine iterative Technik, der Bottom-up-Ansatz genannt wird, uns sowohl Zeit als auch Platz sparen. Beim Bottom-up-Ansatz löst der Computer zuerst die Teilprobleme und verwendet die Teilergebnisse, um zum Endergebnis zu kommen.
Ein Bottom-up-Ansatz zur Erzeugung von Fibonacci-Zahlen sieht so aus:
  • Wenn n gleich 0 oder 1 ist, gib n zurück
  • Ansonsten,
    • Deklariere die Variable twoBehind, um das Ergebnis von (n2) zu speichern und initialisiere sie auf 0
    • Deklariere die Variable oneBehind, um das Ergebnis von (n1) zu speichern und initialisiere sie auf 1
    • Deklariere die Variable result, um das Endergebnis zu speichern und initialisiere sie auf 0
    • Wiederhole (n1) mal:
      • result auf die Summe von twoBehind plus oneBehind aktualisieren
    • twoBehind aktualisieren, um den aktuellen Wert von oneBehind zu speichern
    • oneBehind aktualisieren, um den aktuellen Wert von result zu speichern
    • result zurückgeben
Dieser Ansatz macht keinen rekursiven Aufruf; stattdessen verwendet er Iteration, um die Teilergebnisse zu summieren und die Zahl zu berechnen.
Wenn du die Ausführung des in JavaScript implementierten Bottom-Up Algorithmus sehen möchtest, schau dir dieses Video an oder führe das Program aus.
Der Bottom-up-Algorithmus hat die gleiche O(n) Zeitkomplexität wie der memoisierte Algorithmus, aber er benötigt nur O(1) Platz, da er sich nur drei Zahlen gleichzeitig merkt.

Dynamische Programmierung

Memoisierung und Bottom-up sind beides Techniken aus der dynamischen Programmierung, einer Problemlösungsstrategie aus der Mathematik und Informatik.
Dynamische Programmierung kann verwendet werden, wenn ein Problem eine optimale Substruktur und überlappende Teilprobleme hat. Optimale Substruktur bedeutet, dass die optimale Lösung des Problems aus optimalen Lösungen seiner Teilprobleme berechnet werden kann. Mit anderen Worten: fib(5) kann mit fib(4) und fib(3) gelöst werden. Überlappende Teilprobleme entstehen immer dann, wenn ein Teilproblem mehrfach gelöst wird, was wir gesehen haben, als fib(5) die typischerweise rekursiven Funktionen fib(3) und fib(2) mehrfach aufgerufen hat.
Dynamische Programmierung kann für eine Reihe von Problemen verwendet werden und beinhaltet Techniken neben denen, die wir hier gelernt haben. Wenn du an einem Problem mit optimaler Substruktur und überlappenden Teilproblemen arbeitest, solltest du überlegen, ob ein Ansatz der dynamischen Programmierung funktionieren könnte.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.