Rekursionslimit

[raorao]

Hoi mitenand!

Dass Rekursion mit Python eher vorsichtig zu geniessen ist habe ich an anderer Stelle bereits gefunden. Mir ist natürlich klar, dass folgender Code porblemlos mittels for oder while Schleife geschrieben werden könnte, es geht mir nur ums allgemeine Verständnis für Fälle, in denen die Rekursion weniger einfach zu umgehen ist und aber trotzdem ein hohes Rekursionslimit nötig ist. Trotzdem würde ich gerne begreifen, wieso folgender Code auf meinem Computer nach ca. 9600 Durchläufen einfach abbricht ohne Fehlermeldung!? Kann mir das jemand in einfachem Deutsch erklären. Wieso wird da kein Fehler geworfen?

Code: Alles auswählen

import sys
sys.setrecursionlimit(10000000)

def rec(c):
    c += 1
    if c % 100 == 0:
        print c
    rec(c)

rec(0)

Herzlichen Dank!

[Darii]

Du kriegst keine Warnung, weil das Rekursionslimit nur ein Schutzschild ist, das verhindert, dass du das reale(durch die C-Stackgröße bestimmte) Rekursionslimit tatsächlich überschreitest, damit der Python-Interpreter noch einen Ausnahme werfen kann.

Setzt du das Rekursionslimit hingegen auf irgendeinen viel zu hohen Wert, dann crasht der Interpreter im Zweifelsfall einfach ohne eine Fehlermeldung auszugeben.

Um das zu umgehen kannst du zum einen die Stackgröße heraufsetzen (im Beispiel das Maximum unter OSX)

Code: Alles auswählen

ulimit -s 65532

oder alternativ Stackless Python nehmen, das benutzt nicht den normalen C-Stack und crasht erst viel später.

[BlackJack]

@raorao: Ich komme bis 15800 und das dürfte der gleiche Grund sein, warum folgendes C-Programm bei mir nur bis 261900 kommt (ohne Optimierungen übersetzt):

Code: Alles auswählen

#include <stdint.h>
#include <stdio.h>

void rec(uint32_t n)
{
    n += 1;
    if (n % 100 == 0) printf("%d\n", n);
    rec(n);
}

int main(void)
{
    rec(0);
    return 0;
}

Der C-Aufrufstack ist halt auch begrenzt. Bei mir kommt in beiden Fällen ein "segfault", also ein Abbruch weil das Programm auf Speicher zugreifen möchte, auf den es nicht zugreifen darf.

[Defnull]

...für Fälle, in denen die Rekursion weniger einfach zu umgehen ist...

OT: Soweit ich weiß kann schon per Definition jedes rekursive Problem auch iterativ gelöst werden.

[DasIch]

OT: Soweit ich weiß kann schon per Definition jedes rekursive Problem auch iterativ gelöst werden.

Er hat auch "weniger einfach" gesagt Seinen eigenen Stack zu benutzen ist zwar problemlos möglich aber doch eher schwer verständlich.

[Leonidas]

Naja, da der gezeigte Quelltext ist Endrekursiv also könnte man mal schauen was der TCO-Dekorator bringt.