Maximale Rekursionstiefe

[jmurauer]

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]

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.

[Gromit]

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