Warum hat dieser Code nicht genügend Speicher in Java, aber nicht in c?

Question

in Java oder C kann ich eine Funktion wie

fun(){ 
    fun(); 
} 

(ignorieren Syntax Details)

in Java schreiben I OutOfMemory Ausnahme, sondern in C (und vielleicht einige andere Sprachen) scheint es zu laufen bekommen für immer , als wäre es eine Endlosschleife. Warum bekomme ich nicht auch OutOfMemory Fehler?

Answer 1

Da Ihre Funktion ein Beispiel für tail recursion ist, dann optimiert der C-Compiler höchstwahrscheinlich die Rekursion zur Iteration, was dazu führt, dass die Schleife unendlich läuft, ohne abzustürzen.

Answer 2

In C könnte dies als Tail-rekursive Aufruf optimiert werden. Also nennt sich der Anruf zu fun() nicht wirklich selbst; es startet nur die Funktion neu (wie ein Goto). Mit anderen Worten, behandeln die Compiler es, als ob es so geschrieben worden war:

void fun() { 
start: 
    goto start; 
} 

So wird der Stapel nicht wachsen.

Answer 3

Der Grund warum ist, dass der C-Compiler dies wahrscheinlich als ein Tail-Recusive-Aufruf behandelt und daher die Erstellung eines Stacks für die Ausführung der Funktion vermeidet. Da für den Aufruf kein Stapel aufgebaut ist, wird er von der Rekursion in eine einfache Endlosschleifenausführung umgewandelt. Sie können es erzwingen, einen Stapel aufzubauen, indem Sie es rekursiv machen

int fun() { 1 + fun(); } 

Answer 4

Sie werden eine abnormale Programm Beendigung nach einiger Zeit bekommen. Ihr Code enthält eine unbestimmte Rekursion und jeder Aufruf von fun() setzt zusätzliche Bytes auf den Stack. Abhängig von der Größe Ihres Speichers und Ihren Limits wird die Anwendung nach mindestens 500 Milli-Inch-Anrufen beendet. Dies kann einige Zeit dauern, aber Sie werden eine außerordentliche Kündigung erhalten.

Die Java-VM begrenzt die Rekursionstiefe auf einen bestimmten Wert, daher wird sie bald beendet.

Answer 5

Wenn die Implementierung einer Programmiersprache tail call optimization ist, wird diese Rekursion in eine Schleife kompiliert. Die aktuelle Java-VM hat keine Tail-Call-Optimierung, sodass sie in java.lang.StackOverflowError endet.

Wahrscheinlich wird irgendwann die Java VM eine Tail Call Optimierung haben, weil die funktionalen Programmiersprachen, die auf JVM laufen (Scala, Clojure etc.) davon profitieren würden (zumindest macht sich der Scala Compiler jetzt selbstständig) Tail Call Optimierung für direct recursion, aber AFAIK nicht für indirekte Rekursion).

Answer 6

Ihr C-Compiler verwendet wahrscheinlich Tail-Rekursion. Jedes Mal, wenn Sie eine neue Funktion eingeben, fügt der Computer dem Stapel einen Eintrag hinzu. Dieser Eintrag gibt an, wohin die CPU nach Beendigung der Routine zurückspringen soll. Nun, in dem oben angegebenen Fall, da der Aufruf von fun() innerhalb von fun() der letzte Aufruf in der Funktion ist, kann der c-Compiler den Stack-Push optimieren und statt dessen einen Rückruf erzeugen. Sie können dies tatsächlich verwenden, um eine Schleife zu erstellen:

int foo(int from, int to) 
{ 
    if (from == to) return from; 
    dosomething(); 
    from ++; 
    foo(from, to); 
} 

Viele Sprachen (zB Erlang) haben keine Schleifen überhaupt und stattdessen das obige Verfahren verwenden Schleifen zu erstellen.

Java unterstützt keine Tail-Rekursion.

Answer 7

Wie andere darauf hingewiesen haben, handelt es sich um eine vom C-Compiler durchgeführte Tail-Call-Rekursionsoptimierung.Wie immer hilft es, ein konkretes Beispiel zu betrachten. Ohne Optimierungen aktiviert gcc (v3.4.6) erzeugt den folgenden x86-Assembler-Code: -

fun: 
    pushl %ebp 
    movl %esp, %ebp 
    call fun 
    leave 
    ret 
    .size fun, .-fun 

Hinweis den rekursiven Aufruf zu Spaß(). Wenn dies ausgeführt wird es schließlich überläuft seinen Stapel und Absturz, aber bei -O2 gcc produziert: -

fun: 
     pushl %ebp 
     movl %esp, %ebp 
.L2: 
     jmp  .L2 
     .size fun, .-fun 

Hinweis die Endlosschleife ohne Rückkehrbefehl? Dies wird einfach für immer ausgeführt.

Answer 8

Andere Beantworter sind korrekt, dass es eine Compiler-Magie gibt, die die Tail-Rekursion in Iteration konvertiert, obwohl dies von den Optimierungseinstellungen des Compilers abhängt. In gcc zum Beispiel kompilieren, wenn wir mit gcc -S -O1 someFile.c (da dem Code), erhalten wir die folgende generierte Assembly:

fun: 
.LFB2: 
     pushq %rbp 
.LCFI0: 
     movq %rsp, %rbp 
.LCFI1: 
     movl $0, %eax 
     call fun 
     leave 
     ret 
.LFE2: 
     .size fun, .-fun 

So können Sie sehen, es ist immer noch Anruf mit/leave/ret Anweisungen einen tatsächlichen Funktionsaufruf auszuführen , die den Prozess beenden wird. Sobald Sie weiter mit gcc -S -O2 someFile.c starten die Optimierung starten wir die Magie bekommen:

fun: 
.LFB24: 
     .p2align 4,,10 
     .p2align 3 
.L2: 
     jmp  .L2 
.LFE24:  
     .size fun, .-fun 
     .p2align 4,,15 

Es auf Ihrem Compiler hängt und Ihren Compiler-Einstellungen, so hilft es, mit ihnen befreundet zu sein.