Begrenzt C++ die Rekursionstiefe?

Question

In Python gibt es eine maximale Rekursionstiefe. Es scheint, weil Python ein Interpreter ist, kein Compiler. Hat C++ das gleiche Konzept? Oder ist es nur mit RAM-Limit verbunden?

Answer 1

Das Limit in C++ ist aufgrund der maximalen Größe des Stapels. Das ist in der Regel weniger als die Größe des RAM um einige Größenordnungen, aber immer noch ziemlich groß. (Glücklicherweise werden große Dinge wie die Zeichenfolge Inhalt normalerweise nicht auf dem Stapel selbst gehalten.)

Das Stapellimit ist normalerweise auf Betriebssystemebene einstellbar. (Siehe die Dokumentation für die Shell ulimit, wenn Sie mit Unix arbeiten.) Der Standardwert für dieses System (OSX) ist 8 MB.

[EDIT] Natürlich hilft die Größe des Stacks nicht ganz von selbst, wenn es darum geht, herauszufinden, wie tief Sie rekrutieren können. Um das zu wissen, müssen Sie die Größe des Aktivierungseintrags (oder Datensätze) der rekursiven Funktion (auch Stack-Frame genannt) berechnen. Der einfachste Weg dies zu tun (den ich kenne) ist, einen Disassembler (eine Funktion der meisten Debugger) zu verwenden und die Größe der Stack-Pointer-Anpassungen am Anfang und am Ende jeder Funktion auszulesen. Was ist chaotisch. (Sie können es auf andere Weise - zum Beispiel die Differenz zwischen Zeigern zu Variablen in zwei Aufrufen berechnen - aber sie sind noch fies, vor allem für tragbaren Code. Lesen der Werte aus der Demontage ist einfacher IMO.)

Answer 2

C++ hat eine maximale Rekursionstiefe, begrenzt durch den Stack. Moderne Betriebssysteme sind jedoch in der Lage, einen Userspace-Stack dynamisch zu erweitern, wenn er sich füllt, wodurch die Rekursionstiefe nur durch Speicherplatz und Speicherfragmentierung begrenzt wird.

Answer 3

Ich glaube, das Limit ist die Größe des Stacks auf der Plattform. Von dem, was ich gelesen habe, ist es 8K 8MB standardmäßig auf Linux, aber moderne Kernel können die Stapelgröße dynamisch anpassen.

Answer 4

Es gibt keine Rekursionstiefennachverfolgung oder -grenze in den C- oder C++ - Standards. Zur Laufzeit ist die Tiefe davon abhängig, wie groß der Stack wachsen kann.

Answer 5

Nein, C++ hat keine explizite Rekursionstiefe. Wenn die maximale Stackgröße überschritten wird (standardmäßig 1 MB unter Windows), wird Ihr Stack von Ihrem C++ - Programm überlaufen und die Ausführung wird beendet.

Answer 6

Python hat eine tunable limit auf rekursive Aufrufe, während C++ durch die Stapelgröße begrenzt ist.

Darüber hinaus können viele Sprachen oder Compiler die Tail-Rekursion optimieren, indem sie den Stack-Frame des Aufrufers entfernen, so dass kein zusätzlicher Stack-Speicherplatz verbraucht wird. (In Endrekursion, das einzige, was die aufrufende Funktion tut, ist nach der rekursive Aufruf machen, ist der rekursive Aufruf Rückgabewert zurückzukehren.)

int fact(int n, int accum=1){ 
    if (n==0) return accum; 
    else return fact(n-1,n*accum); //tail recursion here. 
} 

Python nicht optimiert Endrekursion (aber stackless Python der Fall ist), und C++ tut nicht Tail-Rekursion-Optimierung, aber ich glaube, dass gcc die Tail-Rekursion optimiert. Die JVM optimiert die Tail-Rekursion nicht, obwohl die Scala-Sprache dies in bestimmten häufig dokumentierten Fällen tut. Scheme und Lisp (und wahrscheinlich auch andere funktionale Sprachen) erfordern, dass die Tail-Rekursion optimiert wird.