How usable is non tail recursive recursion in Scala?

Question

Since non tail recursive recursion calls use stack frames like Java does, I'd be weary to do any recursion that, let's say goes beyond 1,000 times. I would be thus weary to use it for most of things.

Do people actually use non tail recursive recursion in Scala? If so, what are the criteria I can use to determine if it can be non tail recursive?

Also, are there plans to remove this memory restriction in future versions of Scala?

There are lots of situations where facts about the domain mean recursion on the stack is unlikely to be a problem. Take a UI menu tree—if it's deep enough to overflow the stack your program has more serious problems, anyway. — Travis Brown
"Also, are there plans to remove this memory restriction in future versions of Scala?" it's not a language version issue. If you write a call that isn't a tail-call (either recursive or non-recursive), then a stack frame will be needed (to keep the state to continue whatever the computation is after the non-tail-call returns). This is the same for Java and most other languages. — The Archetypal Paul
@Paul: It is however an artefact of the current implementation that you ran out of stack very easily even when the JVM still has loads of heap available, right? In theory at least, the Scala compiler could compile the call in such a way that it will use heap instead of stack to keep the state? — Enno Shioji
Yes, which is why I said 'most languages'. There are languages that do this (e.g. scheme and call/cc, I believe) but the overheads are large. The reason we use stacks rather than the heap all the time is the efficiency of allocation and deallocation. I can't see Scala (or any mainstream language) taking the performance hit on normal calls to allow unlimited recursion, though. — The Archetypal Paul
Almost identical question here: stackoverflow.com/questions/24619987/… — The Archetypal Paul

0__ 0__ · Accepted Answer · 2014-07-08T11:49:33

In the situation where you cannot use single tail recursion, for example because you need to alternative between two functions, a mechanism called trampolining has been described.

A more recent and thorough discussion of this topic can be found in Rúnar Bjarnason's paper Stackless Scala With Free Monads.

Personally, I would go the easy route and revert to imperative style if you really have this situation with >1K depths, e.g. use a mutable collection builder.

How usable is non tail recursive recursion in Scala?

1 Answers