104

From what I have read: The reason is because it is not easy to determine which method will actually be called as we have inheritance.

However, why doesn't Java at least have tail-recursion optimization for static methods and enforce proper way to call static methods with the compiler?

Why doesn't Java have any support at all for tail-recursion?

I am not sure if there is any difficulty here at all.

Regarding the suggested duplicate, as explained by Jörg W Mittag1:

  • The other question asks about TCO, this one about TRE. TRE is much simpler than TCO.
  • Also, the other question asks about what limitations the JVM imposes on language implementations that wish to compile to the JVM, this question asks about Java, which is the one language that is not restricted by the JVM, since the JVM spec can be changed by the same people who design Java.
  • And lastly, there isn't even a restriction in the JVM about TRE, because the JVM does have intra-method GOTO, which is all that's needed for TRE

1Formatting added to call out points made.

Improve this question
7
  • 26
    To quote Eric Lippert: "Features aren't cheap; they are extremely expensive and they must not only justify their own cost, they must justify the opportunity cost of not doing the hundred other features we could have done with that budget." Java was designed in part to appeal to C/C++ developers and tail recursion optimization isn't guaranteed in those languages.
    – Doval
    Commented Feb 4, 2015 at 13:08
  • 5
    Correct me if I am wrong, but is Eric Lippert the designer for C# which has tail recursion optimization?
    – InformedA
    Commented Feb 4, 2015 at 13:31
  • 1
    He's on the C# compiler team, yes.
    – Doval
    Commented Feb 4, 2015 at 13:37
  • 10
    From what I understand, the JIT might do it, if certain conditions are met, maybe. So in practice you can't rely on it. But whether C# does or doesn't have it is immaterial to Eric's point.
    – Doval
    Commented Feb 4, 2015 at 14:03
  • 4
    @InstructedA If you dig a bit deeper, you can see that it's never done in the 32-bit JIT compiler. The 64-bit JIT is newer and smarter in many ways. The even newer experimental compiler (both for 32 and 64-bit) is smarter yet, and will support tail-recursion optimization in IL that doesn't explicitly ask for it. There's another point you need to take into account - JIT compilers don't have a lot of time. They are heavily optimized for speed - application that might take hours to compile in C++ will still need to go from IL to native in a couple hundred ms, at most (at least partially).
    – Luaan
    Commented Feb 5, 2015 at 9:31

5 Answers 5

Reset to default
148

As explained by Brian Goetz (Java Language Architect at Oracle) in this video:

in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them.

Anything that changed the number of frames on the stack would break this and would cause an error. He admits this was a stupid reason, and so the JDK developers have since replaced this mechanism.

He further then mentions that it's not a priority, but that tail recursion

will eventually get done.

N.B. This applies to HotSpot and the OpenJDK, other VMs may vary.

Improve this answer
7
  • 8
    I'm amazed there's such a rather cut and dried answer as this! But it really seems like The answer - it's possible now, for outdated technical reasons it hasn't already been done, and so now we just wait for someone to decide it's important enough to implement.
    – BrianH
    Commented Feb 4, 2015 at 21:20
  • 1
    Why not implement a workaround? Like an under-the-covers label-goto which just jumps to the top of the method call with new values for arguments? This would be a compile-time optimization and would not need to shift the stack frames or cause security violations.
    – James Watkins
    Commented Feb 4, 2015 at 21:45
  • 2
    It will be much better for us if you or someone else here can dig deeper and provide specifically what those "security sensitive methods" are. Thank you!
    – InformedA
    Commented Feb 6, 2015 at 0:39
  • 4
    @InstructedA - see securingjava.com/chapter-three/chapter-three-6.html which contains a detailed description of how the Java Security Manager system worked circa the release of Java 2.
    – Jules
    Commented Feb 8, 2015 at 12:03
  • 3
    One workaround is to use another JVM language. Scala, for example, does this in the compiler, not at runtime.
    – James Moore
    Commented Sep 28, 2016 at 23:12
26

Java doesn't have tail call optimization for the same reason most imperative languages don't have it. Imperative loops are the preferred style of the language, and the programmer can replace tail recursion with imperative loops. The complexity isn't worth it for a feature whose use is discouraged as a matter of style.

This thing where programmers want to sometimes write in a FP-style in otherwise imperative languages only came into vogue in the last 10 years or so, after computers started scaling in cores instead of GHz. Even now, it's not that popular. If I suggested replacing an imperative loop with tail recursion at work, half the code reviewers would laugh and the other half would give a confused look. Even in functional programming, you generally avoid tail recursion unless other constructs like higher-order functions don't fit cleanly.

Improve this answer
10
  • 45
    This answer doesn't seem right. Just because tail recursion is not strictly needed does not mean it wouldn't be useful. Recursive solutions are frequently easier to understand than iteration, but the lack of tail calls means recursive algorithms become incorrect for large problem sizes which would blow the stack. This is about correctness, not performance (trading speed for simplicity is often worth it). As the correct answer notes, the lack of tail calls is due to a weird security model relying on stack traces, not to imperative bigotry.
    – amon
    Commented Feb 4, 2015 at 15:05
  • 4
    @amon James Gosling once said that he wouldn't add a feature to Java unless multiple people requested it, and only then he would consider it. So I wouldn't be surprised if part of the answer really was "you could always use a for loop" (and likewise for first-class functions vs objects). I wouldn't go so far as to call it "imperative bigotry" but I don't think it would've been in very high demand back in 1995 when the top concern was probably Java's speed, and lack of generics.
    – Doval
    Commented Feb 4, 2015 at 15:47
  • 7
    @amon, a security model strikes me as a legitimate reason not to add TCO to a pre-existing language, but a poor reason not to design it into the language in the first place. You don't throw out a major programmer-visible feature in order to include a minor behind-the-scenes feature. "Why doesn't Java 8 have TCO" is a very different question than "Why didn't Java 1.0 have TCO?" I was answering the latter.
    – Karl Bielefeldt
    Commented Feb 4, 2015 at 16:21
  • 4
    @rwong, you can transform any recursive function to an iterative one. (If I may, I have written an example here)
    – alain
    Commented Feb 4, 2015 at 22:14
  • 4
    @ZanLynx it depends on the type of problem. For example Visitor pattern can benefit from TCO (depending on specifics of structure and visitor) while having nothing to do with FP. Going through state machines is similar though transformation using trampolines seems slightly more natural (depending on problem). Also while you can, technically, implement trees using loops I believe the consensus is that recursion is much more natural (similar for DFS though in this case you may avoid recursion due to stack limits even with TCO).
    – Maja Piechotka
    Commented Feb 5, 2015 at 4:43
7

Java don't have tall call optimization because the JVM does not have a bytecode for tail calls (to some statically unknown function pointer, e.g. a method in some vtable).

It looks like for social (and perhaps technical) reasons, adding a new bytecode operation in the JVM (which would make it incompatible with earlier versions of that JVM) is terribly difficult to the owner of the JVM spec.

Technical reasons for not adding a new bytecode in the JVM spec include the fact that real-life JVM implementations are terribly complex software pieces (e.g. because of the many JIT optimizations it is doing).

Tail calls to some unknown function requires replacing the current stack frame with a new one, and that operation should sit in the JVM (it is not only a matter of changing the bytecode generating compiler).

Improve this answer
3
  • 19
    The question isn't about tail calls, it's about tail recursion. And the question isn't about the JVM bytecode language, it's about the Java programming language, which is a completely different language. Scala compiles to JVM bytecode (among others) and has tail-recursion elimination. Scheme implementations on the JVM have full Proper Tail-Calls. Java 7 (JVM Spec, 3rd Ed.) added a new bytecode. IBM's J9 JVM performs TCO even without needing a special bytecode.
    – Jörg W Mittag
    Commented Feb 4, 2015 at 16:59
  • 1
    @JörgWMittag: That's true, but then, I wonder if it's really true that the Java programming language doesn't have proper tail calls. It might be more accurate to state that the Java programming language doesn't have to have proper tail calls, in that nothing in the spec mandates it. (That is: I'm not sure that anything in the spec actually forbids an implementation from eliminating tail calls. It's simply not mentioned.)
    – ruakh
    Commented Feb 5, 2015 at 1:45
  • With tail recursion, if a recursive call is immediately followed by a return in the byte code, it should be possible to replace the call with a goto to the beginning of the function. Even if this happens in more than one place. The byte code verifier might have fun with that, and a JIT compiler might make unwarranted assumptions. I wonder whether the pattern where f() contains a statement “return g()” isn’t much more common. Now that might sometimes be fixed nicely with inlining.
    – gnasher729
    Commented Sep 30, 2023 at 22:13
5

Unless a language has a special syntax for making a tail call (recursive or otherwise) and a compiler will squawk when a tail call is requested but cannot be generated, "optional" tail-call or tail-recursion optimization will yield situations where a piece of code may require less than 100 bytes of stack on one machine, but more than 100,000,000 bytes of stack on another. Such a different should be considered qualitative rather than merely quantitative.

It's expected that machines may have differing stack sizes, and thus it's always possible for code to work on one machine but blow the stack on another. Generally, however, code which will work on one machine even when the stack is artificially constricted will likely work on all machines with "normal" stack sizes. If, however, a method which recurses 1,000,000 deep is tail-call optimized on one machine but not another, execution on the former machine will likely work even it its stack is unusually small, and fail on the latter even if its stack is unusually large.

Improve this answer
2

I'd think tail call recursion is not used in Java mainly because doing so would alter the stack traces and therefore make debugging a program much harder. I think one of Java's primary goals is to allow programmers to easily debug their code, and stack tracing is essential to doing that especially in a highly object oriented programming environment. Since iteration could be used instead, the language committee must have figured it's not worth adding tail recursion.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.