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

Surely you'd first get a stack overflow exception (in Java at least).

Answer 2

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 3

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.

Answer 4

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 5

You will get an abnormal program termination after some time. Your code contains an indefinitive recursion and each call to fun() put sadditional bytes on the stack. Depending on the size of your memory and your limits, the application will terminate after at least some 500 mil calls. This might take some time, but you will get an exceptional termination.

The java VM limits the depth of recursion to some level, therefore it will terminate soon.

Answer 6

If a programming language's implementation has tail call optimization, then it will compile that recursion into a loop. The current Java VM does not have tail call optimization, so it will end up in java.lang.StackOverflowError.

Probably some time in the future the Java VM will have tail call optimization, because the functional programming languages which run on JVM (Scala, Clojure etc.) would benefit from it (right now at least the Scala compiler does its own tail call optimization for direct recursion, but AFAIK not for indirect recursion).

Answer 7

Your c compiler is probably using using tail recursion. Every time you enter into a new function the computer adds an entry to the stack. This entry states where the CPU should jump back to after the routine is done. Now in the case given above, since the call to fun() inside fun() is the last call in the function the c compiler may be optimzing out the stack push and instead and creating a tailcall. You can actually use this to create a loop:

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

Many languages (for example Erlang) don't have loops at all and instead use the above method to create loops.

Java does not support tail recursion.

Answer 8

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 9

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.