Zitat:
Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“
Was soll das heissen? rekursiv bedeutet doch nicht, dass man bereits vorhandene Ergebnisse ignorieren und bereits erfolgte Rechenschritte jedesmal von neuem machen muss.
Die Berechnung erfolgt in der rekursiven Variante 100% rekursiv, aber selbstverständlich wird eine vernünftige Implementierung JEDES Algorithmus auf bereits vorhandene Ergebnisse zurückgreifen und die nicht neuerlich berechnen, und das gilt natürlich genauso für iterative Verfahren.
Zitat:
Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr.
Die findet sich bei der Initialisierung des Feldes: Feld[0] := 0. Feld[1] := 1. Damit werden die Anfangswerte sowohl für das iterative als auch für das rekursive Verfahren gesetzt, und ich erspare mir in beiden Funktionen die Abfrage auf Sonderwerte.
Zitat:
Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
beruht oder aufbaut, „tauglich implementiert“ werden?
Das Ergebnis (stark ansteigende Laufzeit) beweist eben, dass die Implementierung untauglich ist. Wenn Du die berechneten Zwischenergebnisse speicherst, und direkt abrufst, falls es sie schon gibt, hast Du aus der untauglichen Implementierung eine taugliche Implementierung des GENAU GLEICHEN Algorithmus gemacht. Diese taugliche Implementierung ist dann im wesentlichen gleich schnell wie ein tauglich implementiertes iteratives Verfahren, und sicher viel schneller, als wennn Du in das iterative Verfahren irgend einen unnötigen Unfug einbaust, der die Laufzeit hinaufschnellen lässt.
Zitat:
Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft.
Nicht der Algorithmus hat das schlechtere Laufzeitverhalten, sondern eben Deine Implementierung. Sobald der Designfehler bei der Implementierung korrigiert ist, ist das Laufzeitverhalten gleich gut.