|
Einsendung:
Ist die iterative Version schneller?
Übrigens hat mir noch ein Freund gesagt, daß die iterative Version weitaus schneller sei als die rekursive. Stimmt das? Liegt das an der Speicherverwaltung? Ich meine, die Funktion muß sozusagen immer "warten", bis die Funktion, die sie selbst aufgerufen hat, einen Rückgabewert liefert, und so entsteht eine komplexe Verästelung und jede Funktion muß warten, bis die Unterfunktion einen Rückgabewert liefert. Tja, Rekursion ist eine komplexe Sache
Das Wartenmüssen ist nicht böse. Die Schleife kann auch erst dann einen neuen Durchlauf machen, wenn der alte um ist. In der iterativen Version können die Werte in Prozessor-Registern gehalten werden. Das macht schnell. In der rekursiven gibt es ganz viele Funktionsaufrufe. Die sind langsam. Und sie fressen Speicherplatz (4 Bytes für die Rücksprungadresse pro Aufruf). Außerdem werden die Ergebnisse zwischengespeichert (noch einmal 4 Bytes pro Aufruf). Diese ganzen Speicherzugriffe machen langsam. Sehr viele rekursive Funktionen lassen sich in iterative Funktionen umsetzen. Das geht sogar automatisch. Bei Compilern für Lisp oder Prolog ist das etwas ganz normales. Leider habe ich diese Optimierung noch an keinem C++-Compiler gesehen. Und in der Implementierung
int fibonacci(int n)
{
if (n==1)
return 1;
else if (n==2)
return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}; |
wird jedesmal, wenn fibonacci(n-2) berechnet wird, der Wert ganz normal berechnet, obwohl er bereits in fibonacci(n-1) berechnet wurde. Das macht richtig langsam!
Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann
schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version]
[inhalt]
[index]
[Fehlerkorrektur, Verbesserungsvorschlag]
© Volkard Henkel <volkard@normannia.de>,
last update: 08/25/00
|
|