Algorithmuspro

Rekursion: der Fibonacci-Aufrufbaum

Zwei rekursive Aufrufe pro Schritt lassen einen Baum aus Aufrufen wachsen und zeigen viel doppelte Arbeit.

Zeit: O(2ⁿ)
Speicher: O(n)

// Schritt für Schritt

Schritt 1 / 13

1function fib(n) {2  if (n <= 1) return n;3  return fib(n - 1) + fib(n - 2);4}

calls: = 1

Rufe fib(4) auf. Es braucht zuerst fib(3) und fib(2).

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

fib(n) ruft fib(n − 1) und fib(n − 2) auf, die Aufrufe verzweigen sich also zu einem Baum. Jeder Aufruf wartet, bis beide Kinder zurückkehren, und addiert dann ihre Ergebnisse. Schau genau hin: Dieselben Teilprobleme tauchen immer wieder auf. Schon bei n = 4 wird fib(2) zweimal berechnet, und der Baum verdoppelt sich ungefähr mit jedem weiteren n. Das ist O(2ⁿ) Zeit. Dynamische Programmierung löst das, indem sie sich Antworten merkt.

Dieses Muster erkennen üben →