Rekursiver Aufruf - Was geht da eigentlich vor sich?

[Namenloser]

Zitat von internetnavigator:

Nun sollte die Effektivität verglichen werden.
Ich war der Auffassung, dass die iterative Methode effektiver arbeitet und habe dazu den oben genannten Satz geschrieben.

Ist die Aussage des Lehrers "so" immer noch suboptimal?

Mal aus Spaß, ein kleines Testprogramm zusammengehackt:

Delphi-Quellcode:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Windows;

function fib_it (pZahl: integer): integer;
var
lAktuell, lVorgaenger1, lVorgaenger2, lZaehl: integer;
begin
lAktuell := 1;
if (pZahl > 2) then begin
lVorgaenger1 := 1;
for lZaehl := 3 to pZahl do begin
  lVorgaenger2 := lVorgaenger1;
  lVorgaenger1 := lAktuell;
  lAktuell := lVorgaenger1 + lVorgaenger2;
  end; {*for*}
end; {* if *}
result := lAktuell;
end;

function fib_rek(pZahl:Integer):Integer;
begin
if pZahl < 3 Then Result := 1
Else Result := fib_rek(pZahl-1) + fib_rek(pZahl-2);
end;


var
  CounterFreq: int64;
  CounterStart: int64;
  CounterEnd: int64;
  s: string;
const
  c = 40;
begin
  if not QueryPerformanceFrequency(CounterFreq) then
    raise Exception.Create('Performance counter not available');
  repeat
    QueryPerformanceCounter(CounterStart);
    WriteLn(fib_it(c));
    QueryPerformanceCounter(CounterEnd);
    WriteLn(Format('Iterative: %.3f ms',
      [(CounterEnd-CounterStart) / CounterFreq*1000]));
    QueryPerformanceCounter(CounterStart);
    WriteLn(fib_rek(c));
    QueryPerformanceCounter(CounterEnd);
    WriteLn(Format('Recursive: %.3f ms',
      [(CounterEnd-CounterStart) / CounterFreq*1000]));
    readln(s);
  until s <> '';
end.

Ich würde sagen, das Ergebnis ist recht eindeutig
[edit]
Ausgabe des Programms übrigens:

Code:

102334155
Iterative: 0,082 ms
102334155
Recursive: 1005,586 ms

102334155
Iterative: 0,083 ms
102334155
Recursive: 998,986 ms

102334155
Iterative: 0,080 ms
102334155
Recursive: 1004,135 ms

102334155
Iterative: 0,084 ms
102334155
Recursive: 1002,222 ms

[/edit]
Das beweist allerdings noch nicht, dass nicht die gesamte Methode kopiert wird, daher hier noch der generiertse Assembler-Code:

Code:

// Register sichern:
Project2.dpr.25: begin
00408BAC 53               push ebx
00408BAD 56               push esi

00408BAE 8BD8             mov ebx,eax // eax = pZahl
Project2.dpr.26: if pZahl < 3 Then Result := 1
00408BB0 83FB03           cmp ebx,$03
00408BB3 7D08             jnl $00408bbd
00408BB5 B801000000       mov eax,$00000001
00408BBA 5E               pop esi
00408BBB 5B               pop ebx
00408BBC C3               ret 
Project2.dpr.27: Else Result := fib_rek(pZahl-1) + fib_rek(pZahl-2);
00408BBD 8BC3             mov eax,ebx
00408BBF 48               dec eax
00408BC0 E8E7FFFFFF       call fib_rek
00408BC5 8BF0             mov esi,eax
00408BC7 8BC3             mov eax,ebx
00408BC9 83E802           sub eax,$02
00408BCC E8DBFFFFFF       call fib_rek
00408BD1 03F0             add esi,eax
00408BD3 8BC6             mov eax,esi // eax = result

// Aufräumen:
Project2.dpr.28: end;
00408BD5 5E               pop esi
00408BD6 5B               pop ebx

// Zurückkehren
00408BD7 C3               ret

Ein weiterer Nachteil der rekursiven Variante ist übrigens der mögliche Stackoverflow.