Speicherbedarf bei Rekursion



  • Und wodurch entstehen diese Verteuerungen?



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



  • 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 🙂



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



  • ;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>



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



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



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



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



  • ;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.
    🙂



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



  • 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



  • 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


Anmelden zum Antworten