File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
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
Author

Does Java optimise stack usage for tail recursion

Tim Cooke
Rancher

Joined: Mar 28, 2008
Posts: 526
    
  23

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
internet detective
Marshal

Joined: May 26, 2003
Posts: 29255
    
140

Tim,
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 .


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
chris webster
Bartender

Joined: Mar 01, 2009
Posts: 1479
    
  11

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: http://aspose.com/file-tools
 
subject: Does Java optimise stack usage for tail recursion
 
Similar Threads
NullPointerException (UnknownSource)
Recursion vs Nested loops.
Discussion on recursion, stack overflows, & compiler optimization for tail recurssion
What does recursion code hurt ?
Find sum of all leaves in a binary search tree