Speicherbedarf bei Rekursion

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*

vielen dank für die blumen ^^

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

knivil

Ja, ich wuerde wohl auch einen Akkumulator benutzen. Aber ich finde die Definition recht elegant.

Bashar schrieb:

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

Hier vielleicht was interessantes: http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl'

knivil schrieb:

In SICP...

SICP ist ja nicht schlecht, wäre aber schöner, wenn die 'ne praxisrelevante programmiersprache (z.b. Java) und für das funktionale zeug Groovy oder so, genommen hätten. (ich meine ja nur, weil wir gerade im Java-forum sind).

knivil schrieb:

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?

potenzieren kommt manchmal vor, aber fakultät oder fibonacci-zahlen suchste im alltag der meisten programmierer vergeblich. in standard-libraries gibt's noch nicht mal fertige funktionen für sowas.

knivil

(ich meine ja nur, weil wir gerade im Java-forum sind)

Deswegen auch mein Link auf joelonsoftware, um die Verbindung herzustellen.

potenzieren kommt manchmal vor, aber fakultät oder fibonacci-zahlen suchste im alltag der meisten programmierer vergeblich. in standard-libraries gibt's noch nicht mal fertige funktionen für sowas.

Naja, die Fibonaccifolge stammt aber aus einem sehr praktischen Kontext. Und vielleicht liegt das auch daran, dass die meisten Programmierer eher mit dem Web zu tun haben. Fibonacci-Heaps sind durchaus praxisrelevant. Auch wikipedia liefert genuegend Beispiele.

@volkard:
Blöde Frage vielleicht, aber was genau hat die iterative Berechnung von Fibonacci-Zahlen mit dem Durchlauf einer verketteten Liste, der durch ein Kompositum umgesetzt wird zu tun?