@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
Eingabe: 08 und 09 funktionieren nicht
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.
- birkenfeld
- Python-Forum Veteran
- Beiträge: 1603
- Registriert: Montag 20. März 2006, 15:29
- Wohnort: Die aufstrebende Universitätsstadt bei München
Was hat Quicksort mit rekursiver Fakultät zu tun?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.
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.