Gibt es eine hard-wired limit auf Rekursionstiefe C
Das Programm in der Diskussion versucht zu berechnen sum-of-first-n-natural-numbers
mit recursion
. Ich weiß, dies kann mit einer einfachen Formel n*(n+1)/2
aber die Idee hier ist, zu verwenden recursion
.
Das Programm ist wie folgt:
#include <stdio.h>
unsigned long int add(unsigned long int n)
{
return (n == 0) ? 0 : n + add(n-1);
}
int main()
{
printf("result : %lu \n", add(1000000));
return 0;
}
Das Programm funktionierte gut für n = 100,000
aber wenn der Wert der n
wurde erhöht 1,000,000
es resultierte ein Segmentation fault (core dumped)
Der folgende Auszug wurde aus dem gdb
Nachricht.
Program received signal SIGSEGV, Segmentation fault.
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8
) at k.c:4
Meine Frage(N):
-
Gibt es eine hard-wired limit auf
recursion depth
imC
? oder hat dierecursion depth
hängt von den verfügbaren stack-Speicher? -
Was sind die möglichen Gründe, warum ein Programm erhalten würde, ein reSIGSEGV signal?
- für zwei Fragen, schreiben Sie bitte zwei Fragen. Frage 1 wahrscheinlich Duplikate stackoverflow.com/q/2630054/1025391
Du musst angemeldet sein, um einen Kommentar abzugeben.
In der Regel die Grenze wird die Größe des stack. Jedes mal, wenn Sie eine Funktion aufrufen, die eine bestimmte Höhe des Stapels ist gegessen (in der Regel abhängig von der Funktion). Die Menge gegessen wird der stack-frame, und es wird wiederhergestellt, wenn die Funktion zurückgibt. Die stack-Größe ist fast schon fast behoben, wenn das Programm startet, wird entweder angegeben durch das Betriebssystem (und oft auch einstellbar ist), oder sogar hardcoded im Programm.
Einigen Implementierungen kann eine Technik, bei der Sie zuordnen kann, der neue stack-Segmente zur Laufzeit. Aber im Allgemeinen, Sie nicht.
Einige Funktionen verbrauchen stack in etwas mehr unvorhersehbare Weise, wie bei der Zuweisung einer variable-Länge-array gibt.
Einige Funktionen werden kompiliert, um die Verwendung der tail-Aufrufe in einer Weise, die beibehalten wird, Stapelspeicher. Manchmal können Sie schreiben Sie Ihre Funktion so, dass alle Anrufe (wie zu sich selbst) geschehen, wie das Letzte, was er tut, und erwarten, dass der compiler zu optimieren.
Ist es nicht einfach, genau zu sehen, wie viel stack-Speicher benötigt wird für jeden Aufruf einer Funktion, und es werden vorbehaltlich der Optimierungsstufe des Compilers. Eine billige Art und Weise zu tun, dass in Ihrem Fall wäre zu drucken
&n
jeder Zeit seinen genannt;n
wird wahrscheinlich auf dem stack (vor allem, da das Programm braucht, um seine Adresse -- es könnte sonst sein, in einem register), und der Abstand zwischen aufeinander folgenden locations wird es geben die Größe des stack-Frames.1)der Verbrauch von stack erwartet wird, reduziert werden, und geschrieben, als tail-Rekursion Optimierung.
gcc -O3 prog.c
Gibt es keine theoretische Grenze zu Tiefe Rekursion in C. Die einzigen Grenzen sind die Ihrer Umsetzung, in der Regel beschränkt Stapelspeicher.
(Beachten Sie, dass der C-standard eigentlich nicht erfordern, dass eine stack-basierte implementation. Ich kenne keine real-world-Implementierungen, die nicht stack-basiert, aber im Kopf behalten.)
Einem SIGSEGV kann verursacht werden durch eine beliebige Anzahl von Dingen, sondern mehr über Ihre stack-limit ist eine relativ Häufig ein. Die Dereferenzierung eine schlechte Zeiger ist eine andere.
C-standard nicht definiert die minimal erforderliche Tiefe für Funktionsaufrufe. Wenn es Tat, das ist sehr schwer zu garantieren trotzdem, er hätte es schon irgendwo erwähnt, die in Abschnitt
5.2.4 Ökologische Grenzen
.