Efficiency comparison of recursion and non recursive function in Java

Question

As I understand, recursive functions are generally less efficient than equivalent non-recursive functions because of the overhead of function calls. However, I have recently encountered a text book saying this is not necessary true with Java (and C#).

It does not say why, but I assume this might be because the Java compiler optimizes recursive functions in some way.

Does anyone know the details of why this is so?

Answer 1

The text book is probably referring to tail-call optimization; see @Travis's answer for details.

However, the textbook is incorrect in the context of Java. Current Java compilers do not implement tail-call optimization, apparently because it would interfere with the Java security implementation, and would alter the behaviour of applications that introspect on the call stack for various purposes.

References:

• Does the JVM prevent tail call optimizations?
• This Sun bug requesting tail-call support ... still open.
• This page (and the referenced paper) suggest that perhaps it wouldn't be that hard after all ...

There are hints that tail-call optimization might make it into Java 8.

Answer 2

This is usually only true for tail-recursion (http://en.wikipedia.org/wiki/Tail_call).

Tail-recursion is semantically equivalent to an incremented loop, and can therefore be optimized to a loop. Below is a quote from the article that I linked to (emphasis mine):

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate. The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization. In functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops