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:

Codezeile	Rekursive Aufrufe	Total 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 left parenthesis, n, minus, 1, right parenthesis, !, times, 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, left parenthesis, 1, right parenthesis 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:

Codezeile	Rekursive Aufrufe	Total 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, plus, 1) und die Zahl danach ist 2 (aus 1, plus, 1), und so weiter.

Die ersten 10 Fibonacci Zahlen:

0, comma, 1, comma, 1, comma, 2, comma, 3, comma, 5, comma, 8, comma, 13, comma, 21, comma, 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 start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, space, e, x, t, f, i, b, o, n, a, c, c, i, left parenthesis, n, minus, 2, right parenthesis 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, equals, 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 start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis
- 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, equals, 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, equals, 5 bis zu n, equals, 10:

n	Original	Memoisiert
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

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 start text, t, w, o, B, e, h, i, n, d, end text, um das Ergebnis von left parenthesis, n, minus, 2, right parenthesis zu speichern und initialisiere sie auf 0
- Deklariere die Variable start text, o, n, e, B, e, h, i, n, d, end text, um das Ergebnis von left parenthesis, n, minus, 1, right parenthesis zu speichern und initialisiere sie auf 1
- Deklariere die Variable start text, r, e, s, u, l, t, end text, um das Endergebnis zu speichern und initialisiere sie auf 0
- Wiederhole left parenthesis, n, minus, 1, right parenthesis mal:
  - start text, r, e, s, u, l, t, end text auf die Summe von start text, t, w, o, B, e, h, i, n, d, end text plus start text, o, n, e, B, e, h, i, n, d, end text aktualisieren
- start text, t, w, o, B, e, h, i, n, d, end text aktualisieren, um den aktuellen Wert von start text, o, n, e, B, e, h, i, n, d, end text zu speichern
- start text, o, n, e, B, e, h, i, n, d, end text aktualisieren, um den aktuellen Wert von start text, r, e, s, u, l, t, end text zu speichern
- start text, r, e, s, u, l, t, end text 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, left parenthesis, n, right parenthesis Zeitkomplexität wie der memoisierte Algorithmus, aber er benötigt nur O, left parenthesis, 1, right parenthesis 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.

[Attribution]

Willst du an der Diskussion teilnehmen?

Anmelden

Sortiere nach:

Noch keine Beiträge.

Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.