Rekursion | Wie ist eine Rekursion nachzuvollziehen?



  • 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