Efficiency comparison of recursion and non recursive function in Java

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 som开发者_StackOverflowe way.

Does anyone know the details of why this is so?

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.

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

Some reasons why recursive implementations can be as efficient as iterative ones under certain circumstances:

• Compilers can be clever enough to optimise out the function call for certain functions, e.g. by converting a tail-recursive function into a loop. I strongly suspect some of the modern JIT compilers for Java do this.
• Modern processors do branch prediction and speculative execution, which can mean that the cost of a function call is minimal, or at least not much more than the cost of an iterative loop
• In situations where you need a small amount local storage on each level of recursion, it is often more efficient to put this on the stack via a recursive function call than to allocate it in some other way (e.g. via a queue in heap memory).

My general advice however is don't bother worrying about this - the difference is so small that it is very unlikely to make a difference in your overall performance.

Guy Steele, one of the fathers of Java, wrote a paper in 1977

    Debunking the "Expensive Procedure Call" Myth
or, Procedure Call Implementations Considered Harmful
          or, LAMBDA: The Ultimate GOTO

Abstract: Folklore states that GOTO statements are "cheap', while procedure calls are 'expensive'. This myth is largely a result of poorly designed language Implementations.

That's funny, because even today, Java has no tail call optimization:)

To the best of my knowledge, Java does not do any sort of recursion optimization. Knowing this is important - not because of efficiency, but because recursion at an excessive depth (a few thousand should do it) will cause a stack overflow and crash your program. (Really, considering the name of this site, I'm surprised nobody brought this up before me).

I don't think so, in my experience in solving some programming problems in sites like UVA or SPOJ I had to remove the recursion in order to solve the problem within established time to solve the problem.

One way that you can think is: in recursive calls, any time that the recursion occurs, the jvm must allocate resources for the function that has being called, in non recursive functions most part of the memory is already allocated.