Eingabe: 08 und 09 funktionieren nicht

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Granino
User
Beiträge: 19
Registriert: Freitag 10. August 2007, 15:40

@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
BlackJack

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.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

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?
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
BlackJack

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.
Antworten