Das deutsche Python-Forum

Hallo Blackjack,

was ist das denn für eine Programmiersprache (Link)?

Habe ich das mit der Endrekursion richtig verstanden, wenn ich die Fakultät so programmiere
Heißt endrekursiv auch rechtsrekursiv?

Habe aber mal schnell die drei Möglichkeiten programmiert, linear und die beiden rekursiven Arten.
Bei 100 000 Wiederholungen von 100! erhielt ich die Zeiten
t1 = 4,8 Sek; t2 = 9,3 Sek, t3 = 9,2 Sek.
Das heißt, die Art der Rekursion macht bei der Fakultät praktisch nichts aus, was für andere Rekursionen aber nicht gelten muss.

Gruß Granino

Mir sind eben alle Einrückungen und Leerzeichen verlorengegengen. Wie kann ich das korrigieren?

Granino hat geschrieben:Mir sind eben alle Einrückungen und Leerzeichen verlorengegengen. Wie kann ich das korrigieren?

Den Beitrag editieren und ihn in Code-Tags setzen. Da gibts extra Buttons im Editor dafür.

@Granino: Scheint Haskell zu sein.
Dein Beispiel ist nicht endrekursiv. Schau Dir zur Erklärung mal das an:
http://de.wikipedia.org/wiki/Endrekursiv
MfG
HWK

Die Sprache die ich da verwendet habe ist Haskell.

Deine Funktion ist nicht Endrekursiv. Endrekursiv ist eine Funktion, wenn der rekursive Aufruf die letzte Aktion in der Berechnung der Funktion ist. Das ist bei Dir in beiden Fällen nicht der Fall, weil das Ergebnis des rekursiven Aufrufs noch mit `n` multipliziert werden muss, bevor das Ergebnis feststeht.

Endrekursion ist deshalb wünschenswert, weil nach dem rekursiven Aufruf keine der lokalen Variablen mehr benutzt werden, was bedeutet, dass man sie schon vorher freigeben kann. Oder wenn sich die Funktion selbst aufruft, kann man den aktuellen Stack-Rahmen einfach wiederverwenden, womit die Rekursion vom Compiler effektiv zu einer einfachen Schleife übersetzt wird. Das zielt nur indirekt auf die Laufgeschwindigkeit sondern mehr auf den unnötigen Speicherverbrauch auf dem Stack in diesem Fall.

Das gilt allerdings nur für Compiler die auch Endrekursion entfernen, oder auf Englisch "tail call optimization" durchführen. Das macht CPython nicht automatisch. Es gibt aber einen lustigen "Hack" als Dekorator, den man auf eine Funktion anwenden kann, von der man sicher weiss, dass sie endrekursiv ist: Tail Call Optimization Decorator. Der "Hack" verändert nicht den Bytecode sondern erkennt den rekursiven Aufruf und löst eine Ausnahme aus bevor die Funktion erneut aufgerufen wird und verhindert so dass der Stack wächst.

@Leonidas, HWK, Blackjack : Vielen Dank! Wieder etwas gelernt.

@Blackjack: Habe jetzt gerade meine 4. Version der Fakultät geschrieben: Endrekursiv. Ich brauchte sie ja nur von Deinem Link "Tail Call Optimazation Decoration" abschreiben.
Die Rechenzeiten für 100! bei 100 000 Durchläufen sind etwa 9 Sek. für die beiden Rekursionen, ca. 5 Sek. für die Iteration und knapp 11 Sek. für die Endrekursion.
Auf den ersten Blick scheint dies gegen die Endrekursion zu sprechen. Aber bei komplexeren Funktionen mit vielen lokalen Variablen wird es sehr wahrscheinlich - oder bestimmt - anders sein.
Gruß Granino

Ich glaube nicht das es schneller wird. Es wird ja zur Laufzeit mehr gemacht und nicht weniger, wie bei einer statischen "tail call"-Optimierung. Der einzige Vorteil den ich in dem Dekorator sehe, vom Coolness-Faktor mal abgesehen, ist dass der Stack nicht vollgemüllt wird und man nicht an das Rekursionslimit stösst.

Granino hat geschrieben: Ich ärgere mich immer, wenn ich in Lehrbüchern die Fakultät rekursiv programmiert sehe (ohne Hinweis auf die iterative Lösung). Das ist ineffizient und vor allem für den Anfänger schwer zu verstehen. Dagegen empfinde ich den Sortieralgorithmus 'Quicksort' (von Hoare) einfach genial.

Was hat Quicksort mit rekursiver Fakultät zu tun?

Der ist ein besseres Beispiel für Rekursion als Fakultät, da offensichtlicher rekursiv von der Problemstruktur und nicht so einfach durch eine effizientere iterative Variante ersetzbar wie die Fakultät.