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?
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.
subject: Does Java optimise stack usage for tail recursion