Das deutsche Python-Forum

Hallo Community,

Ein Thema in Python finde ich in letzter Zeit sehr interessant. Die Rekursion. Doch mir geht es nicht um eine simple: Sondern, ich weiß nicht wie man sowas nennt, eine verschachtelte. So kommt mir das auf jeden fall vor. Beispiel: Die Ausgabe sieht für mich noch nach zaubern aus, bzw. ich kann sie mir nicht erklären.
Könnte sich vielleicht einer damit auseinandersetzen und mir sagen wie das funktioniert?

Viele Grüße, xpilz

@xpilz: Da ist nichts besonderes bei. Mal Dir den Aufrufstapel auf einem Blatt Papier auf. Wenn Du Dir das erste erklären kannst, verstehe ich nicht was beim zweiten nicht verständlich ist. Da ändert sich doch nicht wirklich etwas.

Das sind 2 Rekursionen _hintereinander_, die sind in keiner Art und Weise verschachtelt.

BlackJack hat geschrieben:Da ist nichts besonderes bei.

cofi hat geschrieben:Das sind 2 Rekursionen _hintereinander_, die sind in keiner Art und Weise verschachtelt.

Irgendwie tu ich mich schwer damit wann die Rekursion aufhört und dir andere anfängt.

BlackJack hat geschrieben:Mal Dir den Aufrufstapel auf einem Blatt Papier auf.

Werde ich wohl malen müssen.

Achja. Ich habe irgendwo schon einmal gelesen das Python im Vergleich zu anderen Sprachen eine gute Rekursion hat. Stimmt das?
Und ist die Rekursion zu empfehlen? Oder sorgt das bei großen Projekten nur für Unverständnis?

mfg, xpilz

xpilz hat geschrieben:Irgendwie tu ich mich schwer damit wann die Rekursion aufhört und dir andere anfängt.

Wenn die 1. abbricht fängt die 2. an und das passiert bei jedem Rekursionsschritt.

xpilz hat geschrieben:Achja. Ich habe irgendwo schon einmal gelesen das Python im Vergleich zu anderen Sprachen eine gute Rekursion hat. Stimmt das?

Nein das ist komplett falsch. Die maximale Rekursionstiefe setzt in Python sogar relativ bald an (1000 per default) und es gibt auch keine Tail Call Optimization, d.h. der Stack wird recht schnell gesprengt weil bei jedem Funktionsaufruf der Stackframe vergroessert wird.

xpilz hat geschrieben:Und ist die Rekursion zu empfehlen? Oder sorgt das bei großen Projekten nur für Unverständnis?

Rekursion ist deshalb nicht zu empfehlen, weil Python nicht dafür gebaut ist (s.o.) Mal ganz abseits davon, dass es ein Konzept ist, das nicht sonderlich leicht zu verstehen ist.

Es gibt schon ein paar Probleme, die rekursiv wesentlich einfacher zu loesen sind; z.B. wenn man mit beliebig tief verschachteten Datenstrukturen arbeitet. Anstonsten wuerde ich immer iterative Varianten bevorzugen.

Eine Sprache mit "guter Rekursion" ist z.B. Scheme. Der Sprachstandard erfordert dort, dass das eine bestimmte Form von Rekursion, die Endrekursion, wo der rekursive Aufruf am Ende eines Ausführungspfads durch eine Funktion steht, zu einem Sprung optimiert werden muss. Damit kann man dort beliebig tiefe Rekursionen haben, weil sie eben gar nicht tief sind, sondern einfache Sprünge sind. Das wiederum ist notwendig, weil unter theoretischen Gesichtspunkten Rekursion und Schleifen gleichwertig sind und Scheme nur Rekursion als Konzept für Schleifen kennt. Würde Scheme die Endrekursion nicht optimieren sondern wie Python die Anzahl der rekursiven Aufrufe auf 1000 beschränken, könnte man dort keine größeren Schleifen bauen, was ziemlich doof wäre.

Python beschränkt das überhaupt nur deswegen, damit fehlerhafte Programme mit endloser Rekursion nicht den gesamten Rechner blockieren, sondern möglichst früh mit einem Fehler abbrechen. Die 1000 sind aber vielleicht im Zeitalter von 4 GB Hauptspeicher nicht mehr zeitgemäß.

Ich persönlich finde rekursive Algorithmen meist einfacher verständlich, da sie (wie bei der Beweistechnik der vollständigen Induktion) nur die Differenz zwischen zwei Schritten angeben. So definiert sich die Fakultät von N etwa dadurch, dass man die Fakultät von N-1 mit N multipliziert. Das ist doch viel einfacher, also zu sagen, ich muss 1 * 2 * 3 * ... * N rechnen.

Stefan

Noch nicht erwähnt wurde hier, dass Funktionsaufrufe in Python relativ teuer sind, d.h. die anfangs nicht wirklich bemerkbare Zeit zum Aufrufen summiert sich mit steigender Rekursionstiefe entsprechend und das kann nach einer Weile durchaus negativ auffallen. Auch ich bin daher der Meinung, dass man sowas in Python vermeiden sollte.

Falls du dich intensiver mit aufwändigen mathematischen Berechnungen beschäftigen willst, solltest du wohl besser den Einsatz entspechend optimierter Module oder gar eine andere Sprache in Erwägung ziehen. Man muss ja nicht alles krampfhaft in Python implementieren.