6

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?

fredley
  • 32,953
  • 42
  • 145
  • 236
katsuya
  • 1,204
  • 3
  • 16
  • 21

6 Answers6

5

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:

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

Community
  • 1
  • 1
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Readers, for more info, see http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations – Michael Easter Mar 11 '11 at 01:49
  • And also see http://stackoverflow.com/questions/3616483/why-does-the-jvm-still-not-support-tail-call-optimization – Raedwald Oct 21 '11 at 12:06
4

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

Travis Webb
  • 14,688
  • 7
  • 55
  • 109
  • I don't know about Java/C#... his book claims this to be the case, but I haven't researched it myself. @Stephen is claiming the opposite. – Travis Webb Mar 11 '11 at 01:02
  • 1
    It might be interesting to know, that scala, which is a language which runs on top of the JVM and produces bytecode, interchangeable with java-bytecode, and with a functional approach, which encourages recursive functions, has a compiler which generates tail-recursive calls. The scala-community would like to see TCO in the JVM itself, but it isn't done yet, not even promised, afaik. However, never forget: Premature optimization is the root of all evil. – user unknown Mar 11 '11 at 01:22
  • 1
    C# does. The support is much better in CLR4 (and works best on 64-bit). However some situations (such as tail-calling to a method with more arguments than the caller) will actually slower as a tail call than as a normal call. – porges Mar 11 '11 at 02:18
  • 1
    The .NET JIT does actually support TCO. See http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx – SimonC Mar 11 '11 at 02:25
4

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.

mikera
  • 105,238
  • 25
  • 256
  • 415
2

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:)

irreputable
  • 44,725
  • 9
  • 65
  • 93
1

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).

Mike Baranczak
  • 8,291
  • 8
  • 47
  • 71
0

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.

JeanK
  • 1,765
  • 1
  • 15
  • 22