Rekursion | Wie ist eine Rekursion nachzuvollziehen?



  • Hallo,
    ich verstehe nicht wie eine Rekursion verläuft. Ich habe mir einige Beispiel Programme aus dem Internet angesehen, aber ich verstehe es nicht. Ich weiß was eine Rekursion ist, aber nicht wie sie verläuft. Eine Rekursion ist selbstaufrufende Funktion.

    Ich picke mir ein Beispiel heraus.

    #include <iostream>       // Für std::cin und std::cout
    
    unsigned int fakultaet(unsigned int zahl) {
         if (zahl <= 1) {
             return 1; // Die Fakultät von 0 und 1 ist als 1 definiert.
         }
    
        return fakultaet(zahl - 1) * zahl;
     }
    
    int main() {
         unsigned int zahl;
    
        std::cout << "Bitte Zahl eingeben: ";
         std::cin >> zahl;                           // Zahl einlesen
         std::cout << "Die Fakultät von " << zahl << // Antwort ausgeben
             " ist " << fakultaet(zahl) << "!" << std::endl;
     }
    
    Ausgabe: 
    
    Bitte Zahl eingeben: <eingabe>4</eingabe>
     Die Fakultät von 4 ist 24!
    

    Quelle:
    http://de.wikibooks.org/wiki/C++-Programmierung/_Weitere_Grundelemente/_Rekursion

    Wie ist die Funktion fakultaet nachzuvollziehen?



  • ...



  • Anfänger53 schrieb:

    ich verstehe nicht wie eine Rekursion verläuft.[...]
    Wie ist die Funktion fakultaet nachzuvollziehen?

    Am besten gar nicht. Ich hab Rekursion erst verstanden, als ich aufgehört habe zu versuchen zu verstehen, wie sie abläuft.



  • Nun, hast due Methode des induktiven Beweises verstanden? Rekursion ist fast das gleich.



  • Bashar schrieb:

    Anfänger53 schrieb:

    ich verstehe nicht wie eine Rekursion verläuft.[...]
    Wie ist die Funktion fakultaet nachzuvollziehen?

    Am besten gar nicht. Ich hab Rekursion erst verstanden, als ich aufgehört habe zu versuchen zu verstehen, wie sie abläuft.

    Ebenso.
    Denke nicht drüber nach, was genau passiert.
    Betrachte einfach den allgemeinen Fall und die Abbruchbedingung.



  • Ich kann dabei keine besondere Schwierigkeit erkennen.
    Löse es wie andere Verständnisprobleme: betrachte, beispielsweise, die verschiedenen Fälle (/Zustände), die an bestimmten Punkten des Programms vorliegen können.
    Oder nimm doch einfach einen Debugger und geh schrittweise durch! 🙂



  • Oh Gott, Leute.
    Jeder der versteht wie ein Programm abgearbeitet wird, speziell wie ein Funktionsaufruf funktioniert, sollte fähig sein Rekursion zu verstehen.
    Ist doch wirklich nichts dabei.

    Rekursion ist etwas was jeder Programmierer verstanden haben sollte. "Am Besten nicht weiter drüber nachdenken" ist kein guter Rat.



  • Ich habs ja auch verstanden.
    Aber nicht, als ich das versucht habe Schritt für Schritt nachzuvollziehen, sondern es "als Ganzes" hinzunehmen. Ist ein wenig schwierig, dass hier zu beschreiben.



  • Gerade das Beispiel ist doch so einfach...

    fak(4) <=> 4 * fak(3) <=> 4 * 3 * fak(2) <=> 4 * 3 * 2 * fak(1) <=> 4 * 3 * 2 * 1



  • Rekursion versteht man erst, wenn man Rekursion versteht. 😃





  • Cybertec schrieb:

    Rekursion versteht man erst, wenn man Rekursion versteht. 😃

    Irgendwie wusste ich, dass noch einer den Spruch bringt... 😃



  • Falls Dir das mit der Fakultät zu abstrakt ist…

    Stell Dir eine Verzeichnisstruktur mit Unterverzeichnissen vor, in der jeweils Dateien liegen.

    Verzeichnis_1
    	Datei_1
    	Datei_2
    	Verzeichnis_2
    		Datei_3
    		Datei_4
    	Datei_5
    

    Du hast eine Funktion LieferAlleDateien( Liste & DateiListe, String Verzeichnis) .

    Die Funktion fügt in die DateiListe alle gefundenen Dateien des übergebenen Verzeichnisses ( Verzeichnis_1 ) ein. Inhalt von DateiListe Datei_1 und Datei_2.

    Wenn eine gefunden Datei ein Verzeichnis ( Verzeichnis_2 ) ist, wird in der Funktion selbige Funktion mit der Liste der bislang gefundenen Dateien und dem Namen des gefundenen Verzeichnisses ( Verzeichnis_2 ) aufgerufen. Es werden die Dateien Datei_3 und Datei_4 in die DateiListe hinzugefügt. Inhalt von DateiListe Datei_1, Datei_2, Datei_3 und Datei_4.

    Die Funktion LieferAlleDateien(…) findet keine weiteren Dateien in Verzeichnis_2 und kehrt zurück in die aufrufende Funktion LieferAlleDateien(…) zurück, welche noch die Datei Datei_5 findet und in die DateiListe anhängt. Inhalt von DateiListe Datei_1, Datei_2, Datei_3, Datei_4 und Datei_5.

    Gruß Helmut



  • Nathan schrieb:

    Aber nicht, als ich das versucht habe Schritt für Schritt nachzuvollziehen, sondern es "als Ganzes" hinzunehmen. Ist ein wenig schwierig, dass hier zu beschreiben.

    Ihr tut so, als wäre Cybertecs Spruch wahr. Als wäre Rekursion was ganz Mystisches, das nur dem Kreis der Erleuchteten nach intensivem Studium zugänglich wäre.

    Ich seh das wie hustbaer. Viel komplizierter als ein ganz normaler Funktionsaufruf ist ein rekursiver auch nicht...



  • Ist es auch nicht.



  • Die Mystik funktioniert aber erstaunlich gut, wie ich finde.

    Eine rekursive Funktion beinhaltet immer eine Fallunterscheidung. Entweder das zu lösende Problem ist trivial, oder es ist nicht trivial und kann irgendwie verkleinert werden. Jetzt die Mystik: Man tut so, als hätte man eine Methode, das verkleinerte Problem zu lösen. Diese Methode ist aber die Funktion, die man gerade schreibt, selbst.

    Das heißt nicht, dass ich nicht weiß, was da abläuft, das ist ja trivial, wenn man Funktionsaufrufe verstanden hat. Es ist nur für mich meistens völlig unproduktiv, darüber nachzudenken.

    Das ganze hat natürlich einen Haken. Das ist eine funktionale Sichtweise. Wenn man Zustand durch die rekursiven Instanzen schleppt, sieht das ganze sehr viel komplizierter aus und man muss sich in der Tat Gedanken über den Ablauf machen. Das ändert aber nichts daran, dass die funktionale Sicht (mit Mystik, wenn man es denn so nennen will) m.E. viel besser für das Verständnis ist als sich dem Thema durch schrittweises Nachvollziehen des Ablaufs, womöglich mit einem Debugger, zu nähern.



  • Nexus schrieb:

    Ihr tut so, als wäre Cybertecs Spruch wahr. Als wäre Rekursion was ganz Mystisches, das nur dem Kreis der Erleuchteten nach intensivem Studium zugänglich wäre.

    Ist es das nicht? 😃

    Nein, im ernst. Natürlich ist der Spruch blödsinn.

    Ich finde nur, das es schwer ist jemanden zu erklären was eine Rekursion ist, obwohl eine Rekursion ansich eigentlich ganz einfach ist.



  • ...



  • Ähm, moment, ich war das nicht der Rekursion nicht versteht.

    Oder meinst du gar nicht mich?



  • Einfache Rekursionen sind doch sehr leicht zu verstehen!

    Berechnung von 2^n:

    n = 1 -> 2^n = 2
    n > 1 -> 2^n = 2 * 2^(n - 1)

    Komplizierter wird es dagegen bei Backtracking und Co (N Damen Problem). Aber da kann man den Umweg über die iterativen Lösung gehen und anhand dessen die Suchraum-Problematik verstehen.

    Als kleine Gemeinheit könnte man dem TE auch die folgende Aufgabe geben.
    A(0, m) = m + 1
    A(n + 1, 0) = A(n, 1)
    A(n + 1, m + 1) = A(n, A(n + 1, m))

    Berechne A(2, 2)

    Und wenn man sich mal einen schönen Nachmittag machen möchte kann man auch A(5, 5) rechnen. 😃


Log in to reply