Rekursiver Aufruf - Was geht da eigentlich vor sich?

[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 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 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 von alzaimar:

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 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.

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 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!
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

[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 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 von NamenLozer:

Zitat von alzaimar:

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 von sx2008:

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 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) ?