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

Donnerstag 30. August 2007, 21:08

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

Code: Alles auswählen

    def fak(n) :
        if n == 1 : 
            return(1)
        else :
            return(n*fak(n-1)        # statt return(fak(n-1)*n)
        #
    #
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
Granino
User
Beiträge: 19
Registriert: Freitag 10. August 2007, 15:40

Donnerstag 30. August 2007, 21:12

Mir sind eben alle Einrückungen und Leerzeichen verlorengegengen. Wie kann ich das korrigieren?
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 30. August 2007, 21:40

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Donnerstag 30. August 2007, 22:20

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

Donnerstag 30. August 2007, 22:44

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.
Granino
User
Beiträge: 19
Registriert: Freitag 10. August 2007, 15:40

Samstag 1. September 2007, 17:43

@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

Samstag 1. September 2007, 18:33

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

Samstag 1. September 2007, 23:33

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

Sonntag 2. September 2007, 08:51

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