Rekursion vs. Iteration

[idefix2]

Zitat:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt

Widerlegt wurde nichts dergleichen, sondern es wurde nur bewiesen, dass eine schlechte Implementierung eines Algorithmus katastrophale Folgen auf die Performance haben kann - und das gilt für rekursive ebenso wie für iterative Verfahren.

Ich habe die Fibonacci-Folge rekursiv und iterativ für die Zahlen 10,20... bis 90 berechnet und ausgegeben (92 ist die grösste Zahl, für die die Fibonacci-Funtion noch in ein int64 passt).

i rec(10*i)
--- --------
1: 55
2: 6765
3: 832040
4: 102334155
5: 12586269025
6: 1548008755920
7: 190392490709135
8: 23416728348467685
9: 2880067194370816120
Zeit: 00:00:00
i iter(10*i)
--- --------
1: 55
2: 6765
3: 832040
4: 102334155
5: 12586269025
6: 1548008755920
7: 190392490709135
8: 23416728348467685
9: 2880067194370816120
Zeit: 00:00:00

Die Zeit, die die beiden Verfahren brauchen, ist vernachlässigbar.
Natürlich, wenn man jedes Zwischenergebnis unzählige Male neu berechnet, geht die Performance in den Keller, aber das hat nicht mit Iteration vs. Rekursion zu tun, sondern nur mit Unfug programmieren.

Delphi-Quellcode:

var
Feld: array [0..92] of int64;

procedure initfeld;
var i: integer;
begin
feld[0] := 0;
feld[1] := 1;
for i := 2 to 92 do
  feld[i] := -1; // noch nicht berechnet
end;

function iter(n: Integer): Int64;
var
  h: Integer;
begin
  if  feld[n] < 0
  then for h := 2 to n do
         if feld[h]<0 then feld [h] := feld[h-1]+feld[h-2];
  result := feld[n];
end;

function rec (n: integer): int64;
begin
  if feld[n]<0
  then feld[n] := rec(n-1)+rec(n-2);
  rec := feld[n];
end;

procedure TMainForm.Button2Click(Sender: TObject);

var
  i: Integer;
  t: TDatetime;
begin
  Memo1.Lines.Clear;
  Memo1.Lines.Add('i   rec(10*i) ');
  Memo1.Lines.Add('--- -------- ');
  initfeld;
  t := now;
  for i := 1 to 9 do
    Memo1.Lines.Add(Format('%2d: %8d ', [i, rec(10*i)]));
  Memo1.Lines.Add('Zeit: '+TimeToStr(now-t));

  Memo1.Lines.Add('i   iter(10*i) ');
  Memo1.Lines.Add('--- --------');
  initfeld;
  t := now;
  for i := 1 to 9 do
    Memo1.Lines.Add(Format('%2d: %8d ', [i, iter(10*i)]));
  Memo1.Lines.Add('Zeit: '+TimeToStr(now-t));
end;