Darf ich mal zusammenfassen, da eine weitere Diskussion wirklich nicht mehr ergiebig scheint
?
Besprochen wurden vor allem zwei Algorithmen für die Berechnung der
n-ten Fibonacci-Zahl. Der erste leitet sich direkt aus der Definition
Code:
f(n) = f(n-1) + f(n-2); f(0) = 0; f(1) = 1
ab und besitzt eine Laufzeit von Θ(fib(n)) = Θ(1.61...^n) (ja, das Ding hat sich selbst als Laufzeit
). Wenn man an "rekursiver Fibonacci" denkt, dürfte man an dessen Implementierung denken.
Haskell
Code:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Da der Algorithmus nicht endrekursiv ist, ist eine iterative Umsetzung nur äußerst umständlich möglich, aber auf jeden Fall machbar und wird genau die gleiche asymptotische Laufzeit ergeben.
Wer aber an "den iterativen Fibonacci" denkt, meint eigentlich einen anderen Algorithmus und eine andere Definition, was auf den letzten Seiten schon mehrmals durch die Birne gesprochen wurde
. Beim Namen genannt hat ihn gammatester schon auf Seite 4:
Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).
Selbst wenn in der fertigen Implementierung keine Matrizen vorkommen, ist der iterative Code
viel näher an dieser Definition als an der vorherigen. Und auch wenn sich Iteration wunderbar eignet, um "wiederhole etwas
n-mal" umzusetzen, geht das genauso gut rekursiv, wie
jfheins gezeigt hat.
Code:
fib n =
loop n 0 1
where
loop 0 x x' = x
loop n x x' = loop (n-1) x' (x+x')
In imperativen Sprachen sicher weniger üblich, aber besitzt auf jeden Fall ebenso lineare Laufzeit und man spart sich das nervende Variablen-Tauschen
. Ein schlauer Compiler wird für beide Implementierungen sowieso genau den gleichen Code erzeugen.
Ich denke, daraus kann man eigentlich nur schlussfolgern, dass beide Vorgehensweisen eine schnelle Implementierung zulassen (wahrscheinlich schnell genug für alle Anwendungen ohne BigInt-Arithmetik, die sowieso andere Laufzeiten erzeugen würde), die Rekursion aber
zusätzlich noch ein Verfahren kennt, das mit seiner Laufzeit kaum punkten kann, aber an Einfachheit und Übersichtlichkeit nicht zu schlagen ist.
Und wer mir jetzt noch erzählen will, ich hätte in einer Sprache, die weder Iteration noch Nebeneffekte kennt, nur "teilrekursiven" Code kennt, dem habe ich nichts mehr zu sagen.