Rekursiver Aufruf - Was geht da eigentlich vor sich?

[internetnavigator]

Guten Abend zusammen!

Ich habe an meiner Schule einen Kurs Informatik belegt.
Ich habe es schriftlich, also schreiben wir Klausuren.

Nur habe ich folgendes geschrieben:

"Eine rekursive Berechnung dauert
[somit] länger; Schon allein dadaurch,
dass die Rücksprungadresse "gehalten"
werden muss, benötigt das Programm mehr Speicher."

Unterstrichenes zeigt den von dem Lehrer makierten Fehler.

Daneben steht:

"es wird eine Kopie der gesamten Methode im Rechenspeicher abgelegt, [...]"

Was ist denn nun richtig? Wird die gesamte Methode kopiert, oder nur die Rücksprungadresse
im Stack "gehalten"?

Ich habe so viele unterschiedliche Ansichten gehört, so dass ich nun garnicht mehr
durchblicke. Was meint ihr ist richtig?

Gruß !N

[Neutral General]

Hi,

Die Rücksprungadresse wird aufm Stack abgelegt, also gespeichert. Alles andere ist Unsinn.

100% sicher.

[Apollonius]

Auf dem Stack landen die Rücksprungadresse sowie die meisten lokalen Variablen. Was soll bitte eine "Kopie der gesamten Methode" sein?

[3_of_8]

Wobei zumindest manche Prozessoren - ich weiß nicht, ob bei den neueren und gebräuchlichen Architekturen immer noch so ist - zyklische Funktionsaufrufscaches haben, in die Rücksprungadressen sowie mehrere lokale Variablen hineinpassen und gar nicht erst in den Hauptspeicher geschrieben werden.

EDIT: Neben den lokalen Variablen müssen natürlich auch die Parameter gespeichert werden.

[Namenloser]

Sehr kompetenter Lehrer :wall:

Ich habe manchmal das Gefühl, dass Lehrer einfach Spaß daran haben, mit dem Rotstift in Arbeiten herumzustreichen - und wenn sie nichts finden, dann streichen sie einfach irgendetwas an - wie bei meiner letzten Englischarbeit: "pseudo-cool" wurde korrigiert zu "pseudo-coole" - WTF? :wall: Und das war nur eine von vielen Stellen... "leider" lag der Fehlerindex trotzdem noch so niedrig, dass er für die Note irrelevant war, weshalb ich auf eine Beschwerde verzichtet habe. Ich habe nämlich leider die Erfahrung gemacht, dass viele Lehrer es überhaupt nicht vertragen können, wenn man ihre Unfehlbarkeit in Frage stellt - Und ich habe wirklich kein Interesse daran, mich mit einem Lehrer anzulegen, den ich wahrscheinlich für die nächsten 3 Jahre nicht loswerde.

In deinem Fall würde ich aber auf jeden Fall darauf bestehen, dass der Lehrer seinen Fehler einsieht, weil er bei dir sicher wesentlich relevanter für die Endnote ist, als die paar vermeintlichen Ausdrucks- oder Grammatikfehler in meiner Englischarbeit. Ich weiß, dass das nicht so einfach ist wie es klingt, weil die meisten Lehrer sich einfach stur stellen - theoretisch könnte man zwar Klage einreichen, aber wer macht das schon...

</rant>

Vielleicht kannst du deinen Lehrer ja mit etwas Fachliteratur überzeugen. Viel Glück.

[Neutral General]

Was heißt "hoffentlich kannst du ihn [...] überzeugen" ??

Der Typ soll sich mal den erzeugten Assembler Code anschauen und vorher nen x86-Assembler Crashkurs machen -.-

[Namenloser]

Zitat:

Zitat von Neutral General

Was heißt "hoffentlich kannst du ihn [...] überzeugen" ??

So läuft es nun mal defacto in der Schule, scheinen viele leider zu vergessen...

[SirThornberry]

Wenn du wirklich unbedingt dein Recht durchbringen willst dann such dir einen Programmierer in deiner Nähe welcher deinem Lehrer einen Besuch abstattet.

[blablab]

Du musst selber einschätzen obs was bringt oder nicht. Es gibt Lehrer bei denen wärs am schlausten einfach die schlechtere Note zu akzeptieren...
Ich hatte au mal so einen Fall, da hab ich ne Aufgabe komplett gelöst und später in der Arbeit hab ich nochmal die Aufgabennummer hingeschrieben und 1,2 zusätzliche Bemerkungen dazu gemacht. Und dann hat er mir die Bemerkung bewertet und die richtige Aufgabe übersehen. Ich bin dann zu ihm hin aber das war ihm völlig egal. Er hat sogar zugegeben dass ers falsch gemacht hat, aber korrigieren kam für ihn net in Frage... Das einzige was du bei solchen Leuten erreichen kannst ist dass sie dich aufm Kieker haben.

[Delphi-Laie]

Ich bin mir nicht so ganz sicher, ob das wirklich alles mit einer bloßen Rücksprungadresse gelöst werden kann.

Ich schreibe jetzt mal so, wie ich es Laie verstehe, und bitte alle Informatiker, mich dafür nicht (virtuell) zu prügeln.

Nehmen wir als trivial(st?)es Beispiel die Fakultät, mathematisch etwas unsauber definiert:

n!=n*n-1 {n>1,2}
n!=n {n=1,2}
n!=1 {n=0,1}

Pascal-spezifischer:

if n>1 (alternativ: >1)
then fak(n):=n*fak(n-1)
(alternativ: result:=n*fak(n-1))
else fak(n):=1

oder komplizierter:

if n>2 (alternativ: >1)
then fak(n):=n*fak(n-1)
(alternativ: result:=n*fak(n-1))
else if n>0 (alternativ: n>1) then fak(n):=n
else if n=0 (alternativ: n>=0) then fak(n):=1

Also, mindestens dieses "n*" muß doch in jedem Falle im (Stack-?!)Speicher zwischengelagert werden, denn die Multiplikation kann doch erst ausgeführt werden, wenn das Ergebnis der Rekursion gelöst wurde (das selbst aus Multiplikationen, Stackspeicherablegungen und -"rückholungen" gewonnen wird).

Es wird also nicht nur eine Methode bzw. ein Zeiger darauf benötigt (wie sie im Quelltext und auch nach der Compilierung vorliegen), sondern es müssen auch konkrete Variablen(inhalte) mit erfaßt werden. Das alles mit einer schönden Rücksprungadresse?! Wohin? Dorthin, wo die Methode und die Variablen abgelegt werden?

Meinte der Informatiklehrer dieses Ablegen von (mindestens) "(result:=)n*" als "Kopie der gesamten Methode"?

[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.ä.)

[3_of_8]

Hier mal eben, der Vollständigkeit halber, die Variante mit (mehr oder weniger) konstanter Laufzeit:

Delphi-Quellcode:

function fib(const n: Integer);
begin
  Result := round((power((1 + sqrt(5)) / 2, n) - power((1 - sqrt(5)) / 2, n))) / sqrt(5));
end;

EDIT: Das Kopieren der ganzen Methode ist im übrigen auch auf modernen Prozessoren praktisch nicht möglich, weil man normalerweise keinen Lesezugriff auf das eigene Programm hat (man müsste das Programm auf der Festplatte suchen und da raus kopieren) und vor allem, weil man nur in den Datenbereich schreiben kann und dieser (zumindest teilweise) durch Dinge wie das NX-Bit nicht einmal ausführbar ist. Also Kopieren ist nicht nur sinnlos, sondern auch praktisch unmöglich.

[alzaimar]

Nu werd ich mal korrigieren:

Zitat:

Zitat von internetnavigator

"Eine rekursive Berechnung dauert
[somit] länger; Schon allein dadaurch,
dass die Rücksprungadresse "gehalten"
werden muss, benötigt das Programm mehr Speicher."

Eine rekursive Berechnung dauert nicht notwendigerweise länger als eine iterativ implementierte Variante, sofern der Algorithmus der gleiche ist. Es gibt hier im Forum einige Diskussionen zu dem Thema: Manchmal bringt es was, die Rekursion 'per Hand' zu kodieren, z.B. mit einem Stack, manchmal nicht. Unterm Strich bleibt der Vorteil, das eine rekursiv implementierte Lösung i.A. *lesbarer* ist.

Natürlich gibt es für jeden rekursiven Algorithmus ein iteratives Äquivalent, welches teilweise völlig anders arbeitet, aber das ist nicht das Thema. Diese iterativen Äquivalente sind manchmal eleganter (Fibionacci), manchmal grauenvoll unleserlich (Ackermann). Von Quicksort kenne ich z.B. gar kein iteratives Äquivalent, das ohne einen selbstimplementierten Stack auskommt.

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.

Ich würde mir mal z.B. hier im Forum weitere Meinung einholen und dann deinen Lehrer mit diesen (unseren) Meinungen konfrontieren. Vielleicht sieht er seinen Fehler ein. Er ist auch gerne eingeladen, sich hier zu dem Thema zu äußern.

Ich würde ihn aber erstmal bitten, seinen Kommentar zu erklären ('Damit ich das verstehe, Herr Lehrer. Ich will ja was lernen. *schleim*")

Zitat:

Zitat von NamenLozer

Mal aus Spaß, ein kleines Testprogramm zusammengehackt:

Du vergleichst Äpfel mit Birnen. Die beiden Algorithmen haben nichts miteinander gemein, bis auf das Ergebnis. Ich kann Dir auch eine iterative Fibionacci-Implementierung bieten. die 312 Jahre rechnet.

[Namenloser]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von NamenLozer

Mal aus Spaß, ein kleines Testprogramm zusammengehackt:

Du vergleichst Äpfel mit Birnen. Die beiden Algorithmen haben nichts miteinander gemein, bis auf das Ergebnis. Ich kann Dir auch eine iterative Fibionacci-Implementierung bieten. die 312 Jahre rechnet.

Nö, ich vergleiche die beiden Implementierungen, die in der Arbeit gegeben waren, um die geht es ja schließlich.

[alzaimar]

Zitat:

Zitat von NamenLozer

Nö, ich vergleiche die beiden Implementierungen, die in der Arbeit gegeben waren, um die geht es ja schließlich.

Hab ich auch grad gesehen. :oops:

Dann muss ich meine Ausführungen korrigieren: Der Lehrer vergleicht Äpfel mit Birnen.

Mal sehen: Eine rekursive Fibionacci-Implementierung, die auch recht flott ist:

Delphi-Quellcode:

Var
  Buffer : Array [0..1000] Of Integer; // Einmalig mit '0' initialisieren

function fib_rek(pZahl:Integer):Integer;
begin
  if Buffer[pZahl]>0 then
    Result := Buffer[pZahl]
  Else if pZahl < 3 Then
    Result := 1
  Else
    Result := fib_rek(pZahl-1) + fib_rek(pZahl-2);

  Buffer[pZahl] := Result;
end;

Probier die mal...

Zitat:

Zitat von Mein Laptop

Iterative: 0,186 ms
Recursive: 0,076 ms

Leider ist aber die Antwort vom Threadersteller in jedem Falle falsch, denn der Grund für die drastischen Performanceunterschiede liegen im Verfahren, Speicherverbrauch hin oder her.

[inherited]

Man kriegt das auch noch effektiver hin. Und damit willkommen beim DP-Fibonacci-Effizienzkontest! :mrgreen:
Heute im Ring: Die iterative Variante, die Standard-Rekursive mit Buffer und eine etwas "aufpoliert" eigene rekursive Variante, auch mit Buffer. Dem Borg seine O(1)-Lösung sei hier außen vor gelassen, die ist ja geschummelt.

Die aufpolierte Fassung macht nichts anderes, als fib(n) = fib(n-1) + fib(n-2) aufzudröseln, denn fib(n-1) ist ja nichts anderes als fib(n-2)+fib(n-3), also ist fib(n) = 2*fib(n-2)+fib(n-3) was dann wieder 3*fib(n-3)+2*fib(n-4) entspricht. Die Koeffizienten sind wiederum Fibonaccizahlen, da allerdings aufsteigende. Das ganze trifft sich dann in der Mitte, und ergibt sich, je nach Teilbarkeit von n durch 2, entweder zu fib(n) = fib(n div 2)*(fib(n div 2 +1)+fib(n div 2 -1)) für ungerade n, oder fib((n+1) div 2)²+fibOwn(n div 2)², was jede Menge Aufrufe spart und das ganze zumindest in dieser Implementation 10 mal schneller als den Iterativen macht.

Und die Testergebnisse für fib(10000) befinden sich, ebenso wie der (schnell'n'dreckige) Code, im Anhang. Die Zahlen in den ProgressBars ist die jeweilige Dauer in ms. Benutzt wird eine olle BigInt-Klasse, weil die da rauskommenden Zahlen doch etwas größer als 2^63-1 sind.

aber vermutlich geht das ganze noch ein Tucken schneller, ich bin gespannt :firejump:

[blablab]

Den vergleich mit rekursiv und iterativ bei der fibonacci folge hatten wir mal und das lief dann auf sowas raus:
Ab nem genügend großen n benötigt die iterative Methode ein paar Minuten/Stunden während es rekursiv so lange dauert wie das Universum alt ist...
Das liegt eben daran dass dir rekursive Methode dieselben Ergebnisse öfter berechnet.

Ich kann sowieso nur von der rekursiven Methode abraten. Deshlab ist mir schon ein Programm regelmäßig abgestürzt wegen StackOverflow. Leider kam keine Fehlermeldung und deshalb saß ich recht lange dran bis ich gemerkt hab worans lag...

[sx2008]

Zitat:

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.

[Delphi-Laie]

Zitat:

Zitat von NamenLozer

Zitat:

Zitat von alzaimar

Zitat:

Zitat von NamenLozer

Mal aus Spaß, ein kleines Testprogramm zusammengehackt:

Du vergleichst Äpfel mit Birnen. Die beiden Algorithmen haben nichts miteinander gemein, bis auf das Ergebnis. Ich kann Dir auch eine iterative Fibionacci-Implementierung bieten. die 312 Jahre rechnet.

Nö, ich vergleiche die beiden Implementierungen, die in der Arbeit gegeben waren, um die geht es ja schließlich.

An dem Vergleich einer Rekursion einer schnöden Gleichung / Formel (letzteres ist ein solch einfaches Konstrukt, daß ich mir nicht sicher bin, ob so etwas überhaupt schon unter Algorithmus fällt), stieß ich mich auch. Nur Rekursion versus Iteration kann m.E. eine sinnvolle Frage und Gegenüberstellung lauten, denn beide beinhalten Wiederholungen, beschreiben bzw. modellieren sie „nur“ anders.

Der Vergleich mit der "Wurzelformel" ist auch aus einem anderen Grunde falsch: Die Berechnung der Wurzel, sofern sie exakt und nicht nur näherungsweise erfolgt, erfordert wegen deren Irrationalität einen unendlich hohen und damit unendlich langen Rechenaufwand (so daß man gar nicht zu den eigentlichen Rechenoperationen mit den Wurzeln als Finale gelangt) und ist damit der irgendwann endenden Rekursion unendlich weit unterlegen!

[alzaimar]

Zitat:

Zitat von sx2008

Zitat:

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?

[Khabarakh]

Man sollte noch eine weitere Rekursionsvariante erwähnen: In #24 hat alzaimar die naive Rekursion durch Memoisation auf die gleiche asymptotische Laufzeit wie die iterative Version gebracht, allerdings mit Θ(n) Speicherverbrauch (genauer: Θ(n) Stack und Θ(n) Heap).

Genauso wie

Zitat:

Zitat von alzaimar

es für jeden rekursiven Algorithmus ein iteratives Äquivalent

gibt es auch immer umgekehrt ein direktes Äquivalent - sonst hätten funktionale Sprachen ohne Schleifen ein echtes Problem -, in diesem Fall:

Delphi-Quellcode:

function Fib(n)
  function Loop(i, j, n')
  begin
    if n' = n then
      Result := i
    else
      Result := Loop(j, i + j, n' + 1);
  end;

  Loop(0, 1, 0);
end;

In Delphi hat diese Variante genau die gleiche Zeit- und Platzkomplexität wie die Memoisationsvariante, der große Witz daran ist aber, dass die Funktion endrekursiv ist (was alzaimar wohl mit "rechtsrekursiv" meinte, den Begriff kenne ich aber nur aus dem Compilerbau). Damit kann ein schlauer Compiler nicht nur durch Tail Calls den linearen Stackverbrauch eliminieren, in solch simplen Fällen sollte er sogar quasi den gleichen Maschinencode erzeugen, egal ob iterativ oder rekursiv!

Natürlich ist diese Variante nicht ganz so leserlich wie die naive Rekursion, aber wenigstens diese dämliche Hilfsvariable entfällt ;P . Vor allem wollte ich eben auf diese direkte Äquivalenz der beiden Methoden hinaus.

Um das ganze mal zusammenzufassen ;) :

Code:

.
                          Zeit                  Stack   Heap
iterativ                  Θ(n)                  Θ(1)    0
/rekursiv mit Tail Calls
naive Rekursion           Θ(fib(n)) = Θ(φ^n)    Θ(n)    0
+ Memoisation             Θ(n)                  Θ(n)    Θ(n)

Aber in welche Klasse fällt denn bitte inheriteds netter Algo, O(log² n) :gruebel: ?

[3_of_8]

Also inherited selbst meinte irgendwas von n log n, aber wenn ich mir das so ansehe, sieht es nach was anderem aus.

Er hat - je nachdem, ob n gerade oder ungerade ist - 2 oder 3 Rekursionsbäume bei jedem Funktionsaufruf und die Rekursionstiefe ist in etwa ld n. Daraus ergibt sich als untere Grenze O(2^(ld n))=O(n) und als obere Grenze O(3^(ld n))=O(3^((log3 n)/(log3 2))=O(n), also O(n)... wenn ich mich jetzt nicht verrechnet habe...

[Khabarakh]

Du darfst die Memoisation nicht vergessen, denn die Aufrufe in der gleichen Rekursionstiefe überlappen sich stark. Wenn ich das richtig sehe, kommen mit jeder Rekursionstiefe höchstens zwei dazu, also insgesamt 2i+1 bei der Tiefe i. Summiert von 1 bis log n also O(log² n).

[sirius]

Nochmal zur Eingangsfrage:
Ich habe hier eine powerpoint-Prä gemacht, welche die Rekursion mal verdeutlichen soll:
http://www.delphipraxis.net/internal...196&highlight=