Why does this code run out of memory in java, but not in c?

Question

In either java or c I can write a function like

fun(){
  fun();
}

(ignoring syntax details)

In java I get OutOfMemory exception but in C (and maybe some other languages) it seems to run forever, as if it were an infinite loop. Why don't I get OutOfMemory error here as well?

Answer 1

Since your function is an example of tail recursion, then most likely, the C compiler is optimizing the recursion to iteration, causing it to loop infinitely without crashing.

Answer 2

Other answerers are correct that there's some compiler magic that converts the tail recursion to iteration, though it depends on the optimization settings of the compiler. In gcc for instance, if we compile with gcc -S -O1 someFile.c (given your code), we get the following generated assembly:

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

So you can see, it's still using call/leave/ret instructions to perform an actual function call, which will kill the process. Once you start optimizing further with gcc -S -O2 someFile.c we start getting the magic:

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

It depends on your compiler and your compiler settings, so it helps to be friends with them.

Answer 3

The reason why is that the C compiler is likely treating this as a tail recusive call and hence avoiding building a stack for the execution of the function. Since no stack is built up for the call it turns from recursion into a simple infinite loop execution. You can force it to build up a stack by making it head recursive

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

Answer 4

As others have pointed out this is a tail call recursion optimization done by the C compiler. As always, it helps to look at a concrete example. Without any optimizations enabled gcc (v3.4.6) produces the following x86 assembly code:-

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

Notice the recursive call to fun(). If this executes it will eventually overflow its stack and crash, but at -O2 gcc produces:-

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

Notice the endless loop without a return instruction? This will simply execute forever.

Answer 5

In C, this could be optimized as a tail-recursive call. So the call to fun() doesn't really call itself; it just restarts the function (like a goto). In other words, the compiler treats it as if it had been written like this:

void fun() {
start:
    goto start;
}

So, the stack will not grow.