Eine Funktion fib(n) für die Fibonacci-Zahlen ist rekursiv definiert als „ist n kleiner oder gleich 1, gib n zurück; andernfalls gib fib(n−1) + fib(n−2) zurück“. Wie oft wird fib beim Aufruf von fib(5) aufgerufen, den ersten Aufruf eingeschlossen?

Antwort: C. 15

Sei C(n) die Zahl der Aufrufe für fib(n). Dann gilt C(0) = C(1) = 1 und C(n) = 1 + C(n−1) + C(n−2), also C(2) = 3, C(3) = 5, C(4) = 9 und C(5) = 15. Weil dieselben Werte immer wieder neu berechnet werden, wächst die Zahl exponentiell mit n; fib(30) verursacht etwa 2,69 Millionen Aufrufe. Mit Memoisation (einer Form der dynamischen Programmierung), die berechnete Werte in einer Tabelle speichert, werden nur die sechs Werte fib(0) bis fib(5) berechnet, und die Aufrufe sinken auf 9 (2n − 1). 6 ist die Zahl der verschiedenen Argumente, und 9 die Zahl der Aufrufe mit Memoisation.