Begrenzt C++ die Rekursionstiefe?

Lesezeit: 7 Minuten

Begrenzt C die Rekursionstiefe
Narek

In Python gibt es eine maximale Rekursionstiefe. Scheint, weil Python eher interpretiert als kompiliert wird. Hat C++ das gleiche Konzept? Oder hängt es nur mit RAM-Limit zusammen?

  • Ich nehme an, du meinst a maximal Rekursionstiefe. (wie tief die Rekursion sein darf, bevor ein Fehler auftritt)

    – jalf

    13. April 2010 um 14:01 Uhr

  • Ich verstehe nicht, warum es etwas damit zu tun haben sollte, ein Interpreter / Compiler zu sein. Zum Beispiel ist Stackless Python immer noch ein Interpreter, verwendet aber nicht den C-Stack für seine Stack-Frames und hat daher nicht das gleiche Problem, oder?

    – Ken

    13. April 2010 um 14:10 Uhr

  • Beachten Sie, dass es C++- und Python-Implementierungen gibt, die Tail-Call-Eliminierungen durchführen können, um in diesen Fällen zu vermeiden, Stack-Limits zu erreichen.

    – jk.

    13. April 2010 um 14:11 Uhr

  • @Ken Stackless erschöpft irgendwann immer noch Ressourcen, wenn der rekursive Aufruf nicht eliminiert werden kann, z. B. Tail-Call-Optimierung

    – jk.

    13. April 2010 um 14:14 Uhr

1646182209 252 Begrenzt C die Rekursionstiefe
Donal Fellows

Die Grenze in C++ liegt an der maximalen Größe des Stacks. Das ist normalerweise um einige Größenordnungen kleiner als die Größe des Arbeitsspeichers, aber immer noch ziemlich groß. (Glücklicherweise sind große Dinge wie Schnur Inhalt werden normalerweise nicht auf dem Stapel selbst gehalten.)

Das Stack-Limit ist normalerweise auf Betriebssystemebene einstellbar. (Siehe die Dokumentation für die ulimit Shell integriert, wenn Sie Unix verwenden.) Der Standardwert auf diesem Computer (OSX) ist 8 MB.

[EDIT] Natürlich hilft die Größe des Stapels nicht ganz allein, wenn es darum geht, herauszufinden, wie tief Sie rekursiv sein können. Um das zu wissen, müssen Sie die Größe der berechnen Aktivierungsaufzeichnung (oder Aufzeichnungen) der rekursiven Funktion (auch Stapelrahmen genannt). Der einfachste Weg, das zu tun (den ich kenne), besteht darin, einen Disassembler zu verwenden (ein Feature der meisten Debugger) und die Größe der Stapelzeigeranpassungen am Anfang und Ende jeder Funktion auszulesen. Was chaotisch ist. (Sie können es auf andere Weise ausarbeiten – zum Beispiel die Differenz zwischen Zeigern auf Variablen in zwei Aufrufen berechnen – aber sie sind noch unangenehmer, insbesondere für portablen Code. Das Auslesen der Werte aus der Disassemblierung ist meiner Meinung nach einfacher.)

  • Ich weiß, ich hätte MiB für die Einheiten sagen sollen, aber das bedeutet für mich etwas ganz anderes. Also nehme ich stattdessen 67,1 Megabit!

    – Donal Fellows

    13. April 2010 um 14:07 Uhr

  • Auf Windows-Rechnern können Sie A. Stapelüberlaufbedingungen sicher handhaben und B. die Stapeltiefe individuell für jede ausführbare Datei festlegen (es ist eine Linker-Option). Unix-Rechner verwenden aufgrund dieser Funktionen standardmäßig viel tiefere Stacks (8 MB) als Windows (1 MB). +1

    – Billy ONeal

    13. April 2010 um 14:08 Uhr


  • Ich denke, dass es auch in diesem Bereich Unterschiede gibt, wie die beiden Betriebssystemfamilien mit virtuellem Speicher umgehen. Die Details beginnen, ziemlich untrivial zu werden.

    – Donal Fellows

    13. April 2010 um 14:14 Uhr

  • Nur zu Ihrer Information für die Leser: Sie haben vielleicht in einigen Kreisen einen “Aktivierungsdatensatz” namens “Stapelrahmen” gesehen 🙂

    – Billy ONeal

    13. April 2010 um 14:15 Uhr

  • hier auf Linux (x86_64), help ulimit sagt, dass die Stapelgröße durch Ausführen abgerufen werden kann ulimit -s was nachgibt 8192relativ zu unlimited ergibt sich durch Ausführen ohne die -s schalten. Der Standardgrenzwert, der verwendet wird, wenn keiner angegeben ist, ist -f: the maximum size of files written by the shell and its children. YMMV auf anderen Unixen [Unices?]aber ich fand es erwähnenswert.

    – Chris Browne

    1. Juni 2012 um 13:44 Uhr

Nein, C++ hat keine explizite Rekursionstiefe. Wenn die maximale Stapelgröße überschritten wird (die unter Windows standardmäßig 1 MB beträgt), wird Ihr C++-Programm Ihren Stapel überlaufen lassen und die Ausführung wird beendet.

  • Ja. +1. Darüber hinaus ist es wichtig zu beachten, dass die Beendigung sofort erfolgt – ähnlich wie beim Aufruf von TerminateProcess. Keine der netten Shutdown-Funktionen Ihres Prozesses (dh DLL_PROCESS_DETACH, DLL_THREAD_DETACH usw.) wird aufgerufen.

    – Billy ONeal

    13. April 2010 um 14:12 Uhr

  • Absolut – dies ist eine der unangenehmsten Möglichkeiten, ein Programm zu beenden.

    – Justin Ethier

    13. April 2010 um 14:17 Uhr

In den C- oder C++-Standards gibt es keine Nachverfolgung oder Begrenzung der Rekursionstiefe. Zur Laufzeit wird die Tiefe dadurch begrenzt, wie groß der Stapel werden kann.

  • Tatsächlich ist die Einschränkung eine Kombination aus der Adressierungsfähigkeit der Plattform, der für den Prozess verfügbaren Speichermenge und etwaigen vom Compiler festgelegten Einschränkungen. Im Allgemeinen können Anwendungen den Stapel überschreiben und undefiniertes Verhalten ausführen.

    – Thomas Matthäus

    13. April 2010 um 16:53 Uhr

  • Auch irgendwelche ulimit-style-Laufzeitbeschränkungen oder im Fall von Threads alle während der Thread-Erstellung festgelegten Beschränkungen. Ich bin mir nicht sicher, ob Sie mit “den Stapel überschreiben” meinen, “auf eine Größe einstellen, die das Betriebssystem nicht unterstützen kann (z. B. unbegrenzt), da zuerst ein anderes Limit erreicht wird” oder “viel zu viel auf den Stapel drücken und das Ende überrennen.” Nichts geht über 256 KB automatischen Speicher in Ihrer rekursiven Funktion, das Überschreiten einer unzureichenden Anzahl von “Nur-Lesen”-Stack-Schutzseiten am Ende und das Erhalten eines Segmentierungsfehlers oder einer Heap-Beschädigung anstelle eines Write-to-Read-Only-Page-Fehlers. ..

    – Mike DeSimone

    14. April 2010 um 3:33 Uhr

Python hat eine einstellbare Grenze bei rekursiven Aufrufen, während C++ durch die Stapelgröße begrenzt ist.

Darüber hinaus können viele Sprachen oder Compiler die Schwanzrekursion optimieren, indem sie den Stack-Frame des Aufrufers entfernen, sodass kein zusätzlicher Stack-Speicherplatz verbraucht wird. (Bei der Schwanzrekursion gibt die aufrufende Funktion nach dem rekursiven Aufruf lediglich den Rückgabewert des rekursiven Aufrufs zurück.)

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

Python optimiert keine Schwanzrekursion (aber Stackless-Python tut), und C++ erfordert keine Schwanzrekursionsoptimierung, aber ich glaube, dass gcc die Schwanzrekursion optimiert. Die JVM optimiert die Schwanzrekursion 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 Schwanzrekursion optimiert wird.

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

  • Hmm.. Ich bin mir nicht ganz sicher, ob Unixen diese Funktion bietet. Aber ich könnte mich sehr sehr irren 🙂 Es scheint boost::regex würde solche Funktionen verwenden, wenn sie verfügbar wären … es verwendet sie unter Windows.

    – Billy ONeal

    13. April 2010 um 14:17 Uhr

  • Dynamische Stapelerweiterung klingt interessant. Haben Sie eine Referenz?

    – Don Wakefield

    13. April 2010 um 14:17 Uhr

  • setrlimit(2) beschreibt ein RLIMIT_STACK Ressource, und die Manpage erwähnt nicht, dass sie Linux-spezifisch ist. linux.die.net/man/2/setrlimit

    – Ignacio Vazquez-Abrams

    13. April 2010 um 14:25 Uhr

  • Ah – ich verstehe warum boost::regex tut es dann nicht. Sie müssen eine einrichten SIGSEGV Handler und fangen alle diese Ausnahmen auf einem alternativen Stack ab, um sie zu behandeln. Und hoffen, dass keine legitime Zugriffsverletzung irgendwo herumliegt.

    – Billy ONeal

    13. April 2010 um 14:32 Uhr


  • Das einzige, was ich in der Vergangenheit über Stack-Erweiterungen gelesen habe, war Paging. Grundsätzlich werden dem Stack keine Seiten (4 KB) zugewiesen, sondern sie werden dynamisch zugewiesen, wenn der Stapelzeiger auf die Schutzseite zugreifen möchte. (Die Schutzseite ist die Seite direkt nach der letzten zugewiesenen Seite). Aber es tut NICHT befreien Sie eine von der Höchstgrenze von 1 MB. Das Limit ist nicht Ihre RAM-Größe.

    – v.oddou

    14. März 2015 um 3:24 Uhr

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

  • Hmm.. Ich bin mir nicht ganz sicher, ob Unixen diese Funktion bietet. Aber ich könnte mich sehr sehr irren 🙂 Es scheint boost::regex würde solche Funktionen verwenden, wenn sie verfügbar wären … es verwendet sie unter Windows.

    – Billy ONeal

    13. April 2010 um 14:17 Uhr

  • Dynamische Stapelerweiterung klingt interessant. Haben Sie eine Referenz?

    – Don Wakefield

    13. April 2010 um 14:17 Uhr

  • setrlimit(2) beschreibt ein RLIMIT_STACK Ressource, und die Manpage erwähnt nicht, dass sie Linux-spezifisch ist. linux.die.net/man/2/setrlimit

    – Ignacio Vazquez-Abrams

    13. April 2010 um 14:25 Uhr

  • Ah – ich verstehe warum boost::regex tut es dann nicht. Sie müssen eine einrichten SIGSEGV Handler und fangen alle diese Ausnahmen auf einem alternativen Stack ab, um sie zu behandeln. Und hoffen, dass keine legitime Zugriffsverletzung irgendwo herumliegt.

    – Billy ONeal

    13. April 2010 um 14:32 Uhr


  • Das einzige, was ich in der Vergangenheit über Stack-Erweiterungen gelesen habe, war Paging. Grundsätzlich werden dem Stack keine Seiten (4 KB) zugewiesen, sondern sie werden dynamisch zugewiesen, wenn der Stapelzeiger auf die Schutzseite zugreifen möchte. (Die Schutzseite ist die Seite direkt nach der letzten zugewiesenen Seite). Aber es tut NICHT befreien Sie eine von der Höchstgrenze von 1 MB. Das Limit ist nicht Ihre RAM-Größe.

    – v.oddou

    14. März 2015 um 3:24 Uhr

906620cookie-checkBegrenzt C++ die Rekursionstiefe?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy