Speicherbedarf bei Rekursion

[der Fragesteller]

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.

[;fricky]

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.

[;fricky]

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.

[;fricky]

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!

[player4245]

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.

[;fricky]

volkard schrieb:

Bei der Baumtraversierung schaut er sich es ein Weilchen an und mag er es von allein rekursiv machen.

nee, er kommt garnicht erst auf die idee, weil er rekursion überhaupt nicht kennt.

player4245 schrieb:

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.

^^ gutes beispiel, ist wenigstens praxisbezogen und keine blosse spielerei mit zahlen u.ä. du solltest info-lehrer werden. *daumen_hoch*

[player4245]

vielen dank für die blumen ^^

[der Fragesteller]

Nun gut. Erneut danke für die vielen Antworten

Ich wollte ja eigentlich nur wissen, ob mein Lehrer Quark geredet hat (was ja offensichtlich der Fall war).
Übrigens wurde als wesentlich cleverere Alternative zum rekursiven Listendurchlauf das Composite-Pattern verwendet. Inwiefern das sinnvoll ist, liegt fernab dessen, was ich beurteilen kann.

MfG
der Fragesteller

[volkard]

der Fragesteller schrieb:

Übrigens wurde als wesentlich cleverere Alternative zum rekursiven Listendurchlauf das Composite-Pattern verwendet. Inwiefern das sinnvoll ist, liegt fernab dessen, was ich beurteilen kann.

Da sind Kraftausdrücke angemessen, fürchte ich.
http://en.literateprograms.org/Fibonacci_numbers_(Java)#Iteration

[Bashar]

player4245 schrieb:

also um einem angehenden programmierer rekursion beizubringen ist das Durchlaufen eines Verzeichnisses doch ein schönes Beispiel.

Stimmt prinzipiell, das hantieren mit den Verzeichnisnamen ist halt ein bisschen umständlich.

[knivil]

Bashar schrieb:

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

Verstehe nicht? In Scheme ist das auch so definiert, bzw. kann ich so implementieren. Scheme ist nicht lazy. In C kann man auch so die Laenge einer einfach verketteteten Liste bestimmen. Der C++ Standard schreibt auch nur vor, dass length() von std::list in O(n) laeuft.

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.

In SICP ist es schon im ersten Kapitel.

http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

player4245 schrieb:

also um einem angehenden programmierer rekursion beizubringen ist das Durchlaufen eines Verzeichnisses doch ein schönes Beispiel.

Ach und mit Fakultaet oder x^n hat noch niemand was zu tun gehabt?

[Bashar]

knivil schrieb:

Verstehe nicht? In Scheme ist das auch so definiert, bzw. kann ich so implementieren.

Genau das ist der springende Punkt. Die Funktion ist nicht endrekursiv, hat also O(n) Stackbedarf. Das "kann man so implementieren", aber niemand der bei Verstand ist tut das.

(Das mit dem lazy ist ein Denkfehler gewesen. Ich hatte das mit foldl/foldr durcheinandergebracht, wo ja entgegen der Intuition die nicht-endrekursive Variante die bessere ist. Soweit ich mich erinnere, weil : ein nicht-strikter Konstruktor ist.)