Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.
Das ist durchaus möglich. Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“ (Die, die Ihr Informatik studiert(et) - gibt es ein Verb dafür?) (worden). Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr. Wenn man einen vollrekursiven Algorithmus teilweise von der Rekursion befreit und sich dann eines Laufzeitverhaltens erfreut, das mit der Iteration mithalten kann - das ist m.E. kein plausibler Nachweis dafür, daß die Rekursion der Iteration ebenbürtig ist?! Denn gerade, weil die Rekursion es eben (vom Laufzeitverhalten bzw. der Komplexität) her nicht ist, ist sie in jenem Algorithmus teilweise entfernt worden.