Maximale Rekursionstiefe

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.
jmurauer
User
Beiträge: 8
Registriert: Mittwoch 22. November 2006, 14:31

Maximale Rekursionstiefe

Beitragvon jmurauer » Montag 4. Dezember 2006, 13:37

Hallo,
ich habe mit den Spaß erlaubt die Ackermann-Funktion zu implementieren. Mit Erstaunen stellte ich fest, dass die Funktion sich sehr bald wegen der Überschreitung der maximalen Rekursionstiefe nicht mehr berechnen lässt.

ackermann(5, 0) geht noch, ackermann(6,0) schon nicht mehr.
ackermann(4,7) ist auch so eine Grenze.

Laut Wikipedia sollte sich mit Java ein ackermann(16,0) berechnen lassen!

Ich habe mir dann die Rekursionstiefe ausgeben lassen, so bei 180000 herum ging es noch.

Ich hab als Vorlage den Pseudocode aus Wikipedia genommen und eins-zu-eins in Python umgesetzt.

Code: Alles auswählen

def ack(n, m):
    '''
    Implementiert die Ackemann-Funktion
    '''
    assert n >= 0
    assert m >= 0
    if n == 0:
        return m + 1
    elif m == 0:
        return ack(n - 1, 1)
    else:
        return ( ack( n-1, ack(n, m-1) ) )


Frage: wo sind die Grenzen von Python (Rekursionstiefe? Speicherbedarf? ...) - kann man das konfigurieren?

Grüße,
Hans
BlackJack

Re: Maximale Rekursionstiefe

Beitragvon BlackJack » Montag 4. Dezember 2006, 14:52

jmurauer hat geschrieben:Ich habe mir dann die Rekursionstiefe ausgeben lassen, so bei 180000 herum ging es noch.


Damit meinst Du jetzt aber nicht die Rekursionstiefe sondern `m`, oder? Die maximale Rekursionstiefe ist nicht so hoch. Man kann sie mit `sys.getrecursionlimit()` abfragen und mit `sys.setrecursionlimit()` setzen. Aber Vorsicht: Wenn dann der C-Stack überlaufen sollte kann es zum Programmabsturz kommen.
Benutzeravatar
Gromit
User
Beiträge: 51
Registriert: Montag 8. Mai 2006, 19:07

Es geht (ein bisschen zumindest)

Beitragvon Gromit » Montag 4. Dezember 2006, 15:11

Mit dem normalen Python kann man die erlaubte Stack-Tiefe zwar abfragen und auch einstellen. Da aber Python für (rekursive) Funktionsaufrufe den C-Stack benutzt, muß dieser für den aktuellen Thread groß genug sein, sonst führt ein zu lax eingestelltes Recursion-Limit je nach Betriebssystem zu Segmentation Faults, Bus Errors oder Allgemeinen Schmutzverletzungen.

Die Funktionen getrecursionlimit und setrecursionlimit aus dem sys-Modul erlauben die Änderung der maximalen Rekursionstiefe.

Will man ohne diese Einschränkung arbeiten, hilft die Verwendung von Stackless Python. Stackless Python verwendet für (rekursive) Pythonaufrufe (meist) nicht den C-Stack.

HTH,
Gerald

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]