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.

Community
  • 1
InformedA
  • 2,991
  • 2
  • 19
  • 28
  • 26
    To quote [Eric Lippert](http://stackoverflow.com/a/4914207/1272233): *"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 Feb 04 '15 at 13:08
  • 5
    Correct me if I am wrong, but is Eric Lippert the designer for C# which has tail recursion optimization? – InformedA Feb 04 '15 at 13:31
  • 1
    He's on the C# compiler team, yes. – Doval Feb 04 '15 at 13:37
  • 10
    From what I understand, [the JIT might do it](http://stackoverflow.com/questions/15864670/generate-tail-call-opcode), [if certain conditions are met](http://blog.cellfish.se/2014/03/tail-recursion-and-c.html), 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 Feb 04 '15 at 14:03
  • @Doval Cheap or expensive is a relative concept depending on the view. As you have mentioned 'opportunity cost' is also by definition a relative cost. Since C# implements it, it means from the relative view of C#, it is cheaper than a few other features that C# doesn't implement but Java does. All in all, the spirit of the question is perhaps can be seen as: what makes it expensive? ggovan has a nice answer below. – InformedA Feb 04 '15 at 15:24
  • 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 Feb 05 '15 at 09:31
  • http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations – Ciro Santilli OurBigBook.com Jun 19 '15 at 12:56

5 Answers5

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.

Derek Mahar
  • 103
  • 3
ggovan
  • 1,619
  • 1
  • 10
  • 9
  • 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 Feb 04 '15 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 Feb 04 '15 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 Feb 06 '15 at 00:39
  • 4
    @InstructedA - see http://www.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 Feb 08 '15 at 12:03
  • Good job @Jiles. Do you have links to the class(es) containing those methods so I can check out the official Oracle's documentation for the latest version and for the future version when optimization is included. That way we can see what change. Hopefully, after that I can put a (+1) and choose this as the answer. – InformedA Feb 09 '15 at 02:14
  • I'm wondering how stacktraces will look like (after exception is thrown) once this is implemented... – Adam Dyga Feb 20 '16 at 21:35
  • 3
    One workaround is to use another JVM language. Scala, for example, does this in the compiler, not at runtime. – James Moore Sep 28 '16 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.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
  • 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 Feb 04 '15 at 15:05
  • @amon: the reason that the designers thought that tail-call optimization were a non-essential feature of a language (and thus, being compromised to make room for other things, such as enabling an implementation shortcut for some security feature), boils down to the observation that a skilled programmer can always transform TCO (and most other recursive calls) into imperative code using suitable data structures. Though, I agree that this answer's mentioning about the GHz is a bit superfluous, given that TCO is strictly a compile-time feature. – rwong Feb 04 '15 at 15:14
  • 4
    @amon James Gosling once said that he wouldn't add a feature to Java [unless multiple people requested it](http://www.gotw.ca/publications/c_family_interview.htm), 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 Feb 04 '15 at 15:47
  • Plus, recursion in idiomatic Java is hardly ever *true* tail-recursion; even `return 1 + m(x)` is not. When have you seen `return m(x)` in method `m`? And everything else is probably a few steps too many for a compiler. (cc @rwong) – Raphael Feb 04 '15 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 Feb 04 '15 at 16:21
  • 4
    @rwong, you can transform **any** recursive function to an iterative one. (If I may, I have written an example [here](http://programmers.stackexchange.com/questions/271513/how-to-convert-the-following-node-evaluation-procedure-to-a-non-recursive-soluti/271551#271551)) – alain Feb 04 '15 at 22:14
  • Using recursion in C or Java always looks like stunt programming to me. No real reason for it, does not fit into the language, and serves only to confuse people. – Zan Lynx Feb 04 '15 at 22:56
  • 4
    @ZanLynx it depends on the type of problem. For example [Visitor pattern](https://en.wikipedia.org/wiki/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). – Maciej Piechotka Feb 05 '15 at 04:43
  • 2
    Really, traversing / processing any recursive datastructure (a list, a tree, a filesystem, an HTML document) can often be naturally expressed in a recursive (although not necessarily tail-recursive) fashion. – Jörg W Mittag Feb 06 '15 at 14:02
  • Nested for loops, IMO, create code that is much harder to reason about. Recursion leads to cleaner solutions much of the time for looping algorithms. – GreenSaguaro Mar 16 '21 at 19:19
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).

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125
  • 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 Feb 04 '15 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 Feb 05 '15 at 01:45
4

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.

supercat
  • 8,335
  • 22
  • 28
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.

annoying_squid
  • 141
  • 6