• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Junilu Lacar
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Ganesh Patekar
  • Tim Moores
  • Pete Letkeman
  • Stephan van Hulst
Bartenders:
  • Carey Brown
  • Tim Holloway
  • Joe Ess

Does Java optimise stack usage for tail recursion  RSS feed

 
Marshal
Posts: 4455
284
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?
 
author & internet detective
Marshal
Posts: 38506
653
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 .
 
Bartender
Posts: 2407
36
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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!