File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Functional Programming and the fly likes Does Java optimise stack usage for tail recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Engineering » Functional Programming
Bookmark "Does Java optimise stack usage for tail recursion" Watch "Does Java optimise stack usage for tail recursion" New topic

Does Java optimise stack usage for tail recursion

Tim Cooke

Joined: Mar 28, 2008
Posts: 2531

chris webster wrote:Also, watch out if you call your purely recursive function with a larger value, as you'll hit problems eventually with all these recursive calls blowing the stack.

This was mentioned over in this thread earlier today where we were discussing how to implement a Factorial calculator using a recursive function in Java. The straight forward linear recursive solution to this problem does indeed suffer with increased stack frame usage for large numbers of n for n!. However, it is possible to implement the solution as a linear iterative function using tail recursion which I know for some languages such as Scheme and Scala result in fixed stack frame usage.

My question is: does Java provide this optimisation for tail recursive functions to use a fixed stack frame?

Tim Driven Development
Jeanne Boyarsky
author & internet detective

Joined: May 26, 2003
Posts: 33107

This post from last year says that Java doesn't optimize tail recursion.

However, Scala does and it runs on a JVM. It "changes" the code a bit to avoid the problem. Which means you could have your Java code call Scala, do your recursion and come back to Java .

[OCA 8 book] [Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
chris webster

Joined: Mar 01, 2009
Posts: 2289

Scala can optimise some tail recursive calls (e.g. Odersky 2008), but only if the function is calling itself, and it's a genuine tail call of course. If TCO is possible, then the Scala recursive call will be compiled down to the equivalent bytecode that would be generated for a loop implementation. If not, then you may only find out your TCO isn't working when you blow the stack at runtime. But you can use the "@tailrec" annotation to tell the Scala compiler you want this to be done, which will cause a compile-time exception if the call cannot be optimised in this way.

Clojure takes a different approach with an explicit recur special form to indicate where recursion should happen in a looping construct. According to Clojure Programming, recur "transfers control to the local-most loop head without consuming stack-space", i.e. it is effectively a recursion control structure, but it does not perform TCO as such. The authors recommend using higher-level looping/iteration forms such as doseq or dotimes where possible, instead of low-level recursion with recur.

Both of these approaches are work-arounds for the JVM, of course.

No more Blub for me, thank you, Vicar.
I agree. Here's the link:
subject: Does Java optimise stack usage for tail recursion
It's not a secret anymore!