Rekursiver Aufruf - Was geht da eigentlich vor sich?

[Wolfgang Mix]

Vielleicht ein bißchchen Trost von mir als Lehrer (nur Hobby-Informatiker).
Es kommt evtl. auch auf das Verhältnis von Lehrer/Schüler an Ich habe bisher
in allen möglichen Programmiesprachen in Grund- und Leistungskursen unterrichtet
und beschäftige mich mit Delphi intensiver erst seit einem Jahr.
Dies habe ich selbstverständlich auch Schüler wissen lassen und
profitiere ständig von Schülern, die in Delphi besser drauf sind
als ich. Ich habe auch hier im Forum, in dem ich mich erst seit
ein paar Monaten beteilige, schon öfter Prügel bezogen, kann damit
aber gut leben und lerne ständig dazu. Bei Klausuren geht es bei uns
nur um den Wissensstand, den wir uns gemeinsam erarbeitet haben.
Wenn ich selbst Unsinn verzapfe, gestehe ich meine Fehler ein und freue
mich auf bessere Lösungen. Richtiger Streß ist bei uns nicht angesagt.


Gruß

Wolfgang - Emil-Possehl-Schule Lübeck

[Namenloser]

Zitat:

Zitat von Wolfgang Mix

...

Da bist du aber leider die Ausnahme.

[3_of_8]

@Delphi-Laie:

Wenn wir mal alle Caches und Optimierungen außen vor lassen, läuft das so ab:

Vor dem (rekursiven) Funktionsaufruf werden Parameter und lokale Variablen auf den Stack gepusht. Bei der Anweisung call schiebt der Prozessor außerdem noch den Wert des Programmzählers + Befehlswortgröße (also 4 auf 32 Bit-Maschinen) auf den Stack, die Rücksprungadresse. Wenn die Unterfunktion ein ret erreicht, wird die Rücksprungadresse gepoppt, dort hingeschrieben und die ganzen lokalen Variablen und Parameter wieder zurückgepoppt.

Was da kopiert wird, ist aber definitiv NICHT die Methode (oder Funktion oder Prozedur, was auch immer), denn das würde ja heißen, dass der komplette Code kopiert wird - und das ist Unsinn.

[internetnavigator]

Ich danke euch alle für eure schnelle Hilfe!

Es ging darum eine interative und eine rekursive Methode von der Art der Berechnung von der Fibonacci-Folge zu vergleichen.

Vorgegebene iterative Methode:

Delphi-Quellcode:

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;

Meine (korrigierte) rekursive Funktion:

Delphi-Quellcode:

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

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?

[3_of_8]

Bei der rekursiven Methode werden vor allem Werte mehrmals berechnet. Wenn die Methode mit 5 aufgerufen wird, wird berechnet: 4 und 3, 3 und 2, 2 und 1 und 2 und nochmal 2 und 1. Sehr ineffizient.

Das mit der Rücksprungadresse stimmt natürlich, im Vergleich zu dem, was ich oben geschrieben habe, macht es aber fast nichts aus. Lokale Variablen gibt es hier nicht zu kopieren, der Parameter wird jedoch auch noch auf dem Stack landen - das hast du nicht geschrieben.

Die Aussage deines Lehrers ist dann korrekt, wenn er mit "Kopie der Methode" tatsächlich "Kopie von Rücksprungadresse und Parameter" meint, was ich aber nicht glaube. Vielleicht hat er es anders gemeint, dann hätte er es aber auch anders schreiben müssen - deine Aussage ist auf jeden Fall richtiger als die deines Lehreres.

(Sohohl die iterative als auch die rekursive - vor allem aber die iterative - Funktion sind nicht sonderlich schön. Allein von der Formatierung - aber die iterative lässt sich auch deutlich eleganter lösen, die if-Abfrage zum Beispiel ist völlig unnötig. (Ich bin mir sicher, der Compiler meckert da sowieso))

[jfheins]

Es ist das richtig, was der Lehrer sagt ;)

Für mich wäre die richtige Antwort "Beide berechnen den Gleichen Wert bei gleichen Parametern. Da nach Effektivität und nicht nach Effizienz gefragt wurde, sind beide Alternativen (gleich) effektiv, da beide das gleiche Resultat erbringen."

Für die rekursive Variante spricht, dass der Code wesentlich einfacher, überschaubarer und verständlicher ist (Aspekte die man nicht unterschätzen sollte)

Für die iterative Variante spricht, dass der Code minimal schneller ist.

Welche Methode "besser" ist, hängt von der Gewichtung der Aspekte ab. (z.B. wie oft wird das aufgerufen? 10000 Mal pro Sekunde - dann ist Geschwindigkeit alles)

[3_of_8]

@jfheins:
Ich glaube der Lehrer wollte nicht hören, dass man an seiner Begriffswahl herummeckert. (Ist aber eine sehr... interessante Lösung :mrgreen: )

Ähem, die rekursive Variante hat (*schnell anschau ohne viel nachzudenken*) sieht mir nach exponentieller Laufzeit aus (wenn man die Nummer des berechneten Folgenglieds betrachtet), da jeder Aufruf zwei Unteraufrufe auslöst bis zu einer Tiefe von n-2. Also sehr ineffizient gegenüber der iterativen Variante mit variablen Laufzeit, macht also viel aus.

Es gibt übrigens auch eine Variante mit konstanter Laufzeit, aber das nur so am Rande. (Bzw. linear, wenn man die Zeit für die Ausgabe mit einbezieht, aber dann wären auch die anderen Varianten schlechter.)

[Khabarakh]

Zitat:

Zitat von 3_of_8

Bei der rekursiven Methode werden vor allem Werte mehrmals berechnet.

Jupp, nämlich fib(n) Stück im Gegensatz zu n bei der iterativen Version, welch Ironie :mrgreen: .

Zitat:

Zitat von jfheins

Für die iterative Variante spricht, dass der Code minimal schneller ist.

Ja, es kommt natürlich immer auf die Umstände an, aber exponentielle gegen lineare Laufzeit fällt für mich trotzdem nicht unter "minimal" ;) .

[edit] Tja, da war ich wohl minimal exponentiell zu langsam :P . [/edit]

[Namenloser]

Zitat:

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 :wink:
[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.

[jfheins]

Zitat:

Zitat von Khabarakh

Ja, es kommt natürlich immer auf die Umstände an, aber exponentielle gegen lineare Laufzeit fällt für mich trotzdem nicht unter "minimal" ;) .

Okay, so genau hab ich mich noch nicht damit beschäftigt - ist gestrichen ;)

Dann könnte man as Lehrer aber immer noch finden, dass der Schüler den eigentlichen Unterschied (linear vs. exponentiell) nicht erkannt hat ...

Ich hatte auch mal so ne Aufgabe - eine Funktion in Java, die irgendwas berechnete und dann ... nichts zurückgab (kein return-Statement) Auf die Frage "Was macht die Funktion" habe ich mir die Antwort "Sie verschwendet Rechenzeit, sonst nichts" aber verkniffen :P

Generell dürfte es nicht besonders gut ankommen wenn du dem Lehrer Inkompetenz vorwirfst und ich würde es lassen falls es nicht wichtig ist. (Versetzung gefährdet o.ä.)