Rekursion | Wie ist eine Rekursion nachzuvollziehen?



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



  • Mit m=5 und n=5 ist doch die Ackermannfunktion bereits nicht mehr zu berechnen oder? 🙂



  • Ehrlich gesagt, habe ich da keine Ahnung mehr.

    Ich glaube (2, 2) war noch einigermaßen parktisch berechenbar. Ab welchem Wert sich der Aufwand weis ich leider nicht mehr. Kann man aber ja mal einfach mittels PC nachrechnen.



  • Bitte ein Bit schrieb:

    Ehrlich gesagt, habe ich da keine Ahnung mehr.

    Ich glaube (2, 2) war noch einigermaßen parktisch berechenbar. Ab welchem Wert sich der Aufwand weis ich leider nicht mehr. Kann man aber ja mal einfach mittels PC nachrechnen.

    Auch für den PC nicht mehr wirklich berechenbar meine ich.
    Und ja, es ist so. Das packt kein Rechner. :p

    Schau mal die Wertetabelle auf Wikipedia an: http://de.wikipedia.org/wiki/Ackermannfunktion



  • Bitte ein Bit schrieb:

    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.

    Naja, das ist genau das was ich sage. Bei solchen Sachen bin ich immer verzweifelt, wenn ich versucht habe, das "iterativ" zu verstehen. Ich würde das wirklich nicht empfehlen.

    Ich würde immer so denken: Der Trivialfall ist ein vollständig gelöstes Brett, d.h. alle n Damen sind platziert. Falls bereits k < n Damen platziert sind, dann sind die ersten k Reihen belegt. Laufe dann durch alle nicht bedrohten Felder in der n+1-ten Reihe und: platziere dort eine Dame und mache den rekursiven Aufruf (das ist das verkleinerte Problem, weil eine Reihe weniger frei ist), nimm danach die Dame wieder weg.

    Als kleine Gemeinheit könnte man dem TE auch die folgende Aufgabe geben.[Ackermann]

    Wozu?

    Ich würde als Anfangsproblem empfehlen, die Türme von Hanoi zu lösen. Auch gut: Alle Permutationen eines Tupels ausgeben.



  • Naja, das ist genau das was ich sage. Bei solchen Sachen bin ich immer verzweifelt, wenn ich versucht habe, das "iterativ" zu verstehen. Ich würde das wirklich nicht empfehlen.

    Meine Sichtweise orientiert sich da eher an der Breitensuche, Tiefensuche, Best-First Search.

    Aber für meinen Geschmack ist das auch relativ egal, ob man solche Rekursionen rekursiv oder iterativ sich verständlich macht.



  • Nathan schrieb:

    Cybertec schrieb:

    Rekursion versteht man erst, wenn man Rekursion versteht. 😃

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

    Also 'praktisches' Beispiel fällt mir da noch ein:
    GNU -> GNU’s Not Unix
    🙂


Anmelden zum Antworten