Rekursion und Iteration

[DarkSean]

function fiboit(n:integer):int64; // iterativ
var f1,f2:int64;
begin
  result := 1;
  f1 := 1;
  f2 := 1;
  for n := 3 to n do
  begin
    result := f1 + f2;
    f1 := f2;
    f2 := result;
  end;
end;

function fiborek(n:integer):int64; // rekursiv
begin
  if (n=1) or (n=2) then
    result := 1
  else
    result := fiborek(n-1) + fiborek(n-2);
end;

Ich habe da eine einfache Frage, nämliche habe ich zwei Problemlösungen entworfen um ein n-tes Glied der Fibonaccifolge zu berechnen. Die eine ist rekursiv, die andere arbeitet iterativ. Warum läuft die iterative Problemlösung so viel schneller ab? (besonders auffällig bei größerem n, z. B. n = 40) Ist es allgemein ökonomischer iterative Problemlösungen zu verwenden?

 

[Dario Linsky]

Hi,

wenn ich raten müsste, würde ich sagen: Mit der Rekursionstiefe wächst auch der Aufruf-Stack bzw. die Verschachtelung der Rücksprungadressen. Bei der Iteration wird die Prozedur nur ein einziges Mal ausgeführt und der Aufruf-Stack verändert sich nicht.

Grüße, D.

Edit:
Siehe auch hier: http://zach.in.tu-clausthal.de/teaching/info1_0506/folien/07_rekursion_6up_2.pdf
Mit n=40 kommt man auf ca. 330 Millionen Funktionsaufrufe. Das dauert schonmal ein bisschen.

 

[RedWing]

Hallo,

ich denke das hat vielmehr mit der Rekursionsart zu tun, als wie mit dem Speicherverbrauch... Deine iterative Variante hat ein lineares Laufzeitverhalten, deine rekursive Variante ist jedoch eine nichtprimitive Rekursion und zeigt dementsprechend exponentielles Laufzeitverhalten. Wenn du deine Rekursion etwas umformst dann kann man die Fibanocci Zahlen mittels einer sogenannten Endrekursion auch in linearer Laufzeit berechnen lassen.

Siehe http://www.mathematik.uni-muenchen.de/~ruckert/fib.html Beispiel für Endrekursion

Gruß,
RedWing

 

[squeaker]

function fiboit(n:integer):int64; // iterativ
var f1,f2:int64;
begin
  result := 1;
  f1 := 1;
  f2 := 1;
  for n := 3 to n do
  begin
    result := f1 + f2;
    f1 := f2;
    f2 := result;
  end;
end;

[

hier wird jeder Wert genau einmal berechnet, d.h. es werden n Werte berechnet.

function fiborek(n:integer):int64; // rekursiv
begin
  if (n=1) or (n=2) then
    result := 1
  else
    result := fiborek(n-1) + fiborek(n-2);
end;

Hier passiert folgendes (am Beispiel von 5):

fib(5) = fib(4)+fib(3) = fib(3)+fib(2) + fib(2)+fib(1) = fib(2)+fib(1)+fib(2)+fib(2)+fib(1)

Wie man hier schon andeutungsweise sieht, wird für fib(5) die Funktion 11 mal aufgerufen (im Gegensatz zu 5 bzw. 5-2 für die Startwerte 1 1). Bei größeren Werten wird das Miß-Verhältnis noch krasser. Das ist der Hauptgrund warum die rekursive Version deutlich langsamer ist.

Zusätzlich kommen noch folgende Effekte hinzu: ein Function-Call/Procedure-Call ist eine relativ kostspielige (in Bezug auf Prozessorzeit) Operation. Und zusätzlich kann der Compiler im Falle der For-Schleife noch sogenanntes "Loop-Unrolling" betreiben und so ein paar Sprünge / Branch-Predictions einsparen.

hier findest du noch ein paar verschiedene Fibonacci-Programme inklusive einer Laufzeitmessung. Insbesondere ist auch ein Endrekursives und ein Explizites Programm dabei.
http://www.mathematik.uni-muenchen.de/~ruckert/fibrun.html

 

[Prodrummer1603]

Ey danke hatte das als hausaufgabe auf, rekursion is ja einfach aber iteration dagegen etwas komplizierter, ich musste das noch nen bisschen anpassen aber es hat funktioniert

 

[dasd]

bin neu im delphi bereich wollte mal rumfragen was eigentlich iteration und rekursion bedeuten

 

[vop]

http://de.wikipedia.org/wiki/Iteration
http://de.wikipedia.org/wiki/Rekursion

Kurz zusammengefasst
Iteration geschieht in Form einer Wiederholung (Schleife)

Rekursion geschieht in Form einer Rückführung des Problems auf sich selbst beispiel:

Traditionelles Beispiel ist in der Mathematik die Fakultät
5! ist dabei das Ergebnis von 1 * 2 * 3 * 4 * 5

Du könntest nun iterativ das Problem lösen (ey das ist keine optimale Lösung sondern einer Erklärung....)

Ergebnis:=1;
for i:=1 to 5 do Ergebnis:=Ergebnis * i;

Oder du kannst das Problem auch rekursiv lösen

function Fakultaet(zahl:longint):longint;
begin
  if zahl = 1 then Result := 1 else Result := zahl * Fakultaet(zahl-1);
end;

In der Rekursion näherst du dich der Lösung, indem du auf eine einfachere Lösung des gleichen Problems zurück greifst.