Zitat von
sx2008:
Zitat von
alzaimar:
Und zum Speicher:
Die Rücksprungadresse wird natürlich auf dem Stack abgelegt, das ist an 'Mehrspeicher' aber auch alles. Das zu erwähnen, ist -finde ich- nicht der Rede wert, aber an sich völlig o.k.
Bist du sicher?
Selbst wenn der Übergabeparameter über ein Register übergeben wird, muss es doch auf dem Stack gesichert werden.
Hätte die Funktion lokale Variablen, wäre der Speicherplatz dafür ebenfalls auf dem Stack alloziert.
Das war misverständlich ausgedrückt: Ich vergleiche die rekursiven Implementierung eines Algorithmus mit einer iterativen Implementierung, die genau das gleiche Verfahren verwendet. Die iterative Implementierung muss den Stack simulieren (Ausnahme: Rechtsrekursion). Das einzige, was
imho ggü. der rekursiven Variante fehlt, ist das merken der Rücksprungadresse.
Natürlich wächst der Stack bei einem rekursiven Aufruf (wie be jedem Aufruf) um die lokalen Variablen zuzüglich der Übergabeparameter sowie der Rücksprungadresse. Etwas analoges müsste man implementieren, wenn man ein Verfahren iterativ programmiert.
Aber wie gesagt: Die Aufgabe des Threaderstellers behandelt gar keine Diskussion "rekursiv vs. iterativ", sondern "langsamer Apfel mit schneller Birne". Beide Früchtchen berechnen die Fibionacci-Zahl Fib(N), der Apfel macht das rekursiv, die Birne (anders) iterativ. "Namenlozer" zeigt, das die Birne viel viel schneller ist. Man könnte also zu dem Ergebnis kommen, das iterativ implementierte Algorithmen stets schneller sind, als ihre rekursiven Pendants.
Genausogut könnte man Bubblesort (iterativ) mit Quicksort (rekursiv) vergleichen: Beide Früchte sortieren, aber die Iterative Variante ist viel viel langsamer. Folgt nun daraus: Iterativ ist langsamer als rekursiv?