Speicherbedarf bei Rekursion

In der heutigen Informatikstunde wurden Vor- und Nachteile von Rekursion besprochen. Nun bin ich mir nicht ganz sicher, ob es stimmt, was da gesagt wurde.
Konkret stellt sich mir folgende Frage:
Bei einem Methodenaufruf in Java sollte es doch - wie in anderen Programmiersprachen - eigentlich nur nötig sein, Rücksprungadresse und Parameter auf den Stack zu legen, zu springen und die Funktion auszuführen. Dabei liegt diese (meines Wissens) nur einmal im Speicher vor (die Methode ist weder static, private oder final, ergo nicht inline), und wird nur mit unterschiedlichen Parametern aufgerufen. Ich gehe davon aus, dass auch in Java diese Methode nicht für jede Klasseninstanz als ein eigenes Stück Code im Speicher liegt, sondern eigentlich nur die darunterliegende Methode mit einem unsichtbaren this-Parameter aufgerufen wird.
Ich hoffe soweit war das alles grob korrekt.

Doch nun zu meiner eigentlichen (In)Fragestellung.
Bei rekursiven Funktionsaufrufen wird - wie bekannt sein dürfte - stets auf eine Abbruchbedingung geprüft. Und ebendiese Abfrage wurde als wichtiger Nachteil von Rekursion (neben dem durchaus hohen Speicherbedarf am Stack) herausgearbeitet. Speziell der durch diese eine Anweisung in die Höhe getriebene Speicherbedarf der Funktion sowie der immense Rechenmehraufwand werden angeprangert.
Ich frage mich nun, ob das so korrekt ist. Dieses eine if (konkret geht es um Rekursion in verketteten Listen) und prüfen auf null sollte doch nur ein einziges Mal wenige Byte Speicher belegen und auch im Bezug auf zusätzlichen Rechenaufwand eher vernachlässigbar sein.

Hat mein Lehrer Recht und täusche ich mich?

MfG,
der Fragesteller

Bashar

der Fragesteller schrieb:

Doch nun zu meiner eigentlichen (In)Fragestellung.
Bei rekursiven Funktionsaufrufen wird - wie bekannt sein dürfte - stets auf eine Abbruchbedingung geprüft. Und ebendiese Abfrage wurde als wichtiger Nachteil von Rekursion (neben dem durchaus hohen Speicherbedarf am Stack) herausgearbeitet. Speziell der durch diese eine Anweisung in die Höhe getriebene Speicherbedarf der Funktion sowie der immense Rechenmehraufwand werden angeprangert.

Nicht nachvollziehbar, insbesondere da diese Abfrage natürlich auch bei einer äquivalenten iterativen Implementation als Schleifenabbruchbedingung auftaucht.

Dieses eine if (konkret geht es um Rekursion in verketteten Listen) und prüfen auf null sollte doch nur ein einziges Mal wenige Byte Speicher belegen [...].

Abgesehen davon natürlich.

Hat dein Lehrer das wirklich so gesagt? Kann ich mir kaum vorstellen, normalerweise klingt Halbwissen doch mindestens halbwegs plausibel.

Danke für deine Antwort, Bashar.

Ich habe extra zweimal nachgefragt und mit ihm geredet, und meinen Standpunkt auch klar gemacht.
Er hat das ganze mit Kopfschütteln und ein paar wenig untermauerten "Da täuscht du dich"s abgetan.

Nun gut, danke für die Bestätigung

volkard

der Fragesteller schrieb:

Speziell der durch diese eine Anweisung in die Höhe getriebene Speicherbedarf der Funktion sowie der immense Rechenmehraufwand werden angeprangert.

Hier sehe ich den Knackpunkt. Rekursive Funktionen sind NICHT immens teurer als iterative. Bei unglücklichen Verhältnissen vielleicht man doppelt so teuer. Aber sie machen nicht allgemein aus einem O(n) kein O(n^2) oder sowas.

Immense Verteurungen geschehen, wenn man bei Fibonaccizahlen das übliche fibIter mit dem üblichen fibRek vergleicht, da wird aus O(n) ein O(1.6^n) und das tut weh. Oh, das tut elend weh.

Und wodurch entstehen diese Verteuerungen?

volkard

der Fragesteller schrieb:

Und wodurch entstehen diese Verteuerungen?

Weil bei einer schlechten Zerlegung in Unterprobleme total viele Unterprobleme entstehen und die ungeschickterweise alle berechnet werden, sogar wenn sie schon innerhalb der selben Berechnung schonmal berechnet wurden.
Mit Rekursion hat man *mehr* Möglichkeiten, hier halt auch mehr Möglichkeiten, was Ungeschicktes zu machen. Man ist aber nicht verpflichtet dazu, man kann's mit Rekursion auch schnell machen.
Die iterative Version kriegt man es nicht so ungeschickt hin (,wenn man nicht besondere Gewalt anwendet), weil man, um es überhaupt hinzukriegen, alte Zwischenergebnisse speichern muß.

Bashar

Naive Algorithmen. Wenn du die Fibonacci-Folge naiv implementierst (also if (n <= 1) return 1; else return fib(n-1)+fib(n-2); ), wird sehr oft dasselbe Ergebnis mehrfach berechnet, z.B. wird ja in fib(n-1) als ersters fib(n-2) berechnet, nach der Rückkehr dann (in fib(n)) gleich nochmal. Weiter unten im Aufrufbaum verschärft sich das noch.
Leider werden solche Beispiele gerne benutzt, um Rekursion einzuführen. Eigentlich sollte die Didaktik dazu Rekursion als Möglichkeit einführen, sehr schnell und sehr einfach (das geht, wenn der Groschen einmal gefallen ist) Probleme mit inhärent rekursiver Struktur zu lösen und DANN die Leute bremsen, mit ihrem neuen Hammer auf alles einzuschlagen, was entfernt wie ein Nagel aussieht. Stattdessen verstehen die Lehrer Rekursion selbst nicht mehr, wählen bescheuerte Beispiele und zählen von vornherein nur die Nachteile auf.

Irgendwie bezeichnend, dass die Fibonacci-Folge im Unterricht als Paradebeispiel für Rekursion angeführt wurde.
Nun gut, jetzt weiß ich wenigstens was ich von diesem Lehrer samt Unterricht zu halten habe.

Danke für die Antworten

volkard

der Fragesteller schrieb:

Nun gut, jetzt weiß ich wenigstens was ich von diesem Lehrer samt Unterricht zu halten habe.

Ja. Eine leckere Möglichkeit, sichere Einsen abzuzocken. Eine sichere Zwei bekommt man, wenn man alles weiß. Eine sichere Eins bekommt man, wenn man darüberhinaus die Schwächen des Lehrers kennt und geeignet in die Antworten einbaut.

der Fragesteller schrieb:

Irgendwie bezeichnend, dass die Fibonacci-Folge im Unterricht als Paradebeispiel für Rekursion angeführt wurde.

die fib.-folge ist doch rekursiv erklärt: http://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge
^^und wird daher gern als einfaches beispiel für das erste rekursive programm von programmieranfängern genommen. didaktisch sehe ich daran nix zweifelhaftes.

volkard

;fricky schrieb:

der Fragesteller schrieb:

Irgendwie bezeichnend, dass die Fibonacci-Folge im Unterricht als Paradebeispiel für Rekursion angeführt wurde.

die fib.-folge ist doch rekursiv erklärt: http://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge

Das ist nur eine der möglichen Definitionen und nicht DIE Definition.

<witz>

int strlen(char *str){
   if(*str=='\0')
      return 0;
   else
      return strlen(str+1)+1;
}

</witz>

Th69

Warum ein Witz?

In funktionalen Sprachen ist 'strlen' genau so definiert:

len [] = 0;
len (x:xs) = (len xs) + 1

(Mathematische) Definition sind ja nicht auf Laufzeit optimiert...

Bashar

Was heißt in funktionalen Sprachen, das ergibt nur Sinn, wenn die Sprache lazy ist. Ansonsten müsste man das endrekursiv machen.

volkard schrieb:

;fricky schrieb:

der Fragesteller schrieb:

Irgendwie bezeichnend, dass die Fibonacci-Folge im Unterricht als Paradebeispiel für Rekursion angeführt wurde.

die fib.-folge ist doch rekursiv erklärt: http://de.wikipedia.org/wiki/Fibonacci-Folge#Definition_der_Fibonacci-Folge

Das ist nur eine der möglichen Definitionen und nicht DIE Definition.

nee, aber rekursiv-fibonacci ist für jeden leicht zu verstehen und kann direkt als programm hingeschrieben werden. wie würdest du denn den kids rekursion beibringen, wenn du informatiklehrer wärst? es sollte ja am anfang nicht zu abstrakt sein.

byto

der Fragesteller schrieb:

Ich frage mich nun, ob das so korrekt ist. Dieses eine if (konkret geht es um Rekursion in verketteten Listen) und prüfen auf null sollte doch nur ein einziges Mal wenige Byte Speicher belegen und auch im Bezug auf zusätzlichen Rechenaufwand eher vernachlässigbar sein.

Der Code-Block belegt natürlich nur einmalig Speicher, und zwar wenn der Classloader die Klasse in den PermGen Space der JVM lädt. Danach ist es irrelevant, wieviele Objekte Du von dieser Klasse erzeugst oder wieviele Methoden Du auf Objekten dieser Klasse aufrufst.
Ein Objekt im Heap definiert sich lediglich aus dem Fully Qualified Class Name einer im PermGen liegenden Klasse + die Werte der Member des Objekts. Das kannst Du leicht überprüfen, indem Du ein Objekt seralisierst und Dir das Ergebnis anguckst.

Fazit: Dein Lehrer ist ein Idiot.

volkard

;fricky schrieb:

wie würdest du denn den kids rekursion beibringen, wenn du informatiklehrer wärst? es sollte ja am anfang nicht zu abstrakt sein.

Hängt ganz von der Zielgruppe ab. Aber was ist an den Fibonacci-Zahlen jetzt besser als an der Faktoriellen? Außerdem würde ich die Langsamkeit der trivialen rekursiven Fibonaccifunktion und die Schnelligkeit der rekursiven Quicksort-Funktion nicht damit begründen, daß da ein zusätzliches if wäre.

Bashar

;fricky schrieb:

wie würdest du denn den kids rekursion beibringen, wenn du informatiklehrer wärst?

Mit einem Problem, bei dem Rekursion angebracht ist natürlich. Türme von Hanoi, das 8-Damen-Problem, Traversieren von Bäumen, Quicksort, Auswerten von arithmetischen Ausdrücken. Ich würde dementsprechend Rekursion auch erst erwähnen, wenn sie mit solchen Aufgaben etwas anfangen können.

Bashar schrieb:

;fricky schrieb:

wie würdest du denn den kids rekursion beibringen, wenn du informatiklehrer wärst?

Mit einem Problem, bei dem Rekursion angebracht ist natürlich. Türme von Hanoi, das 8-Damen-Problem, Traversieren von Bäumen, Quicksort, Auswerten von arithmetischen Ausdrücken. Ich würde dementsprechend Rekursion auch erst erwähnen, wenn sie mit solchen Aufgaben etwas anfangen können.

^^das wäre aber schwieriger, weil die kids dann zwei dinge auf einmal begreifen müssen, nämlich rekursion und 'nen anspruchsvollen algorithmus gleichzeitig. ich finde es besser, wenn man das schrittweise angeht. wenn einer schon weiss, was rekursion ist, auch wenn er noch keine effiziente anwendung kennt, fällt ihm das verstehen rekursiver abläufe später leichter. und für den anfang kann erstmal was ganz einfaches herhalten, wie z.b. fibonacci, fakultät oder sowas.

volkard

;fricky schrieb:

^^das wäre aber schwieriger, weil die kids dann zwei dinge auf einmal begreifen müssen, nämlich rekursion und 'nen anspruchsvollen algorithmus gleichzeitig.

Baumtraversierung anspuchsvoll? Haha. Im Gegenteil. Bei Fibonacci oder Fakultät fragt man einen Nube, wie er das machen mag und er mag es iterativ machen. Bei der Baumtraversierung schaut er sich es ein Weilchen an und mag er es von allein rekursiv machen. Viola!

also um einem angehenden programmierer rekursion beizubringen ist das Durchlaufen eines Verzeichnisses doch ein schönes Beispiel. Mit Verzeichnissen und Dateien hatten die schließlich schon mal zu tun und dadurch können sie sich auf das Prinzip konzentrieren. Letzlich ist ein Verzeichnisbaum einem Suchbaum doch ziemlich ähnlich.