Comparing the efficiency of a recursive and non-recursive function in Java

Question

As I understand it, recursive functions are usually less efficient than equivalent non-recursive functions due to the overhead of function calls. However, I recently came across a tutorial that says this is not necessary for Java (and C #).

He does not say why, but I assume that this may be due to the fact that the Java compiler optimizes recursive functions in some way.

Does anyone know the details why this is so?

Answer 1

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

Tail recursion is semantically equivalent to an incremental cycle and therefore can be optimized for the cycle. The following is a quote from an article I am associated with (focus):

The tail is very important because they can be implemented without adding a new stack stack to the call stack. Most of the frame of the current procedure is no longer needed, and it can be replaced with a tail call frame, modified as necessary. The program can then move on to what is called a subroutine. Generating such code instead of a standard call sequence called tail call elimination , or tail call optimization . In functional programming languages, the elimination of tail calls is often guaranteed by the locale, and this guarantee allows the use of recursion, in particular tail recursion instead of loops

Answer 2

The text book probably refers to tail call optimization; see @Travis for more details.

However, the tutorial is incorrect in the context of Java. Existing Java compilers do not implement tail call optimization, apparently because it will interfere with Java security and change the behavior of applications that introspectively look at the call stack for various purposes.

Literature:

• Does the JVM provide call optimization optimization options?
• This Sun Error requiring tail call support ... is still open.
• This page (and the link to the article) suggests that perhaps it would not be so difficult ...

There are clues that tail optimization could turn into Java 8.

Answer 3

Some reasons why recursive implementations can be as effective as iterative in certain circumstances:

• Compilers can be smart enough to optimize function calls for specific functions, for example. by converting a tail recursive function into a loop. I strongly suspect that some of the modern Java JIT compilers do this.
• Modern processors have branch prediction and speculative execution, which may mean that the cost of calling a function is minimal or, at least, not much more than the cost of an iterative loop
• In situations where you need a small local memory at each recursion level, it is often more efficient to push this onto the stack through a recursive function call than allocate it in some other way (for example, through a queue in the heap memory).

However, my general advice is not worried about this - the difference is so small that it is very unlikely to matter in your overall performance.

Answer 4

Guy Steele, one of the fathers of Java, wrote an article in 1977

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

Annotation: Folklore argues that GOTO statements are “cheap,” while procedure calls are “expensive.” the myth is largely the result of a poorly designed language of Realization.

This is ridiculous because even today Java does not have tail call optimization :)

Answer 5

As far as I know, Java does not perform any recursion optimization. It is important to know this - not because of efficiency, but because recursion at excessive depth (several thousand should do this) will lead to a stack overflow and your program to crash. (Indeed, given the name of this site, I am surprised that no one brought it to me).

Answer 6

I don’t think so, in my experience in solving some programming problems on sites such as UVA or SPOJ I had to remove recursion in order to solve the problem at the set time, to solve the problem.

One way you might think: in recursive calls, at any time when recursion occurs, jvm must allocate resources for the called function, in non-recursive functions, most of the memory is already allocated.