• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Does Java optimise stack usage for tail recursion

 
Tim Cooke
Sheriff
Pie
Posts: 3051
124
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34648
364
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 .
 
chris webster
Bartender
Posts: 2407
33
Linux Oracle Postgres Database Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic