The JVM does not support TCO, and this is even more of a problem because the stack size is the same for all threads. This means that increasing the stack size to allow for deeper recursion is a waste of memory.
However, it is easy to implement TCO in Java. The trick is to build a (linked) list of computational steps, until the terminal condition is found. then, we just have to execute the steps in reverse order. Here is how it may be implemented:
First, we define a class for representing the computational steps:
The TailCall abstract class has two realisations: the Suspend class represent in intermediate step (when the current processing is "suspended" in order to make the next recursive call), and the Return class representing the terminal computation.
Suppose we want to create a method computing the sum of all positive integers below a given value. We could define it as:
The sum method calls a recursive helper method. This will work for about 3000 to 5000 steps (depending upon the system since the default stack size is system dependent). For higher values, it will overflow the stack.
We can use the TailCall class to make this method stack safe:
Now you can call the sum method with any argument value without blowing the stack.
Note however that the @tailrec notation does not do anything beside telling the compiler that you believe the annotated function to be tail recursive (thus being candidate for tail call elimination). Without the annotation, the compiler will silently optimize the function if possible, and proceed without optimizing if not. Adding the annotation is a way to ask the compiler to warn you if you were wrong believing the function is tail call recursive.
Pho Tek wrote:I found that scala has a @tailrec annotation.
Be aware that the @tailrec annotation does not have any functional purpose, i.e. it does not make your tail call optimised when it otherwise is not. All it does is cause the compiler to raise an error if your function is not in the correct format required for optimisation.
Pierre-Yves, what a fascinating solution you posed there. I shall most certainly be implementing this myself just to play with it. I can see how you avoid blowing the stack, but I wonder about Object creation on the heap for very deep recursion? I think some experimentation is in order. However, definitely worthy of a cow.
I can see how you avoid blowing the stack, but I wonder about Object creation on the heap for very deep recursion?
Sure, this involves the creation of many objects. Eventually, for very deep recursion, it might blow the heap. I have never see this happening for up to several millions of recursive steps, but of course, it depends about many factors.
i m currently reading your book FP in Java, it's really cool!
One question for you though.. on the fibonacci implementation with two accumulators
Why , even wtih two accumulators, the code will still end up with a STackOverflow error? is it because java still use the stack even though the last call in the function is a call to itself?
From previous page, i understood that if the last call of a recursive function is a call to itself, nothing needs to be put on the stack?
Yes, it is because although the version using two accumulators is tail recursive, Java does not implement TCE (Tail Call Elimination). So to use recursion in Java, you have the following solutions (some may be combined):
- Ensure that the number of steps will be low. This can be the result of some business condition. It could theoretically blow the stack, but you believe it won't happen with normal data.
- Use recursion for cases that can't blow the stack. For example on a balanced binary tree. As the number of objects will be equal to 2 at the power of the recursion depth (something like 2^ 3000), it'll blow the heap long before it exhausts the stack.
- Configure a larger stack. But this is a waste of space in most cases, and anyway, you can go very far in this direction.
- Use the trampoline implementation and tail recursion as I explained. But some recursive computations may not be replaced with tail recursive one.
- Use a language that implements TCO/TCE. This does not mean you have to switch to another language. You could put you tail recursive functions in a library written in Scala and call it from your Java code. Or (much) better, you can write your recursive code in Kotlin. This is not to say that Kotlin is better than Scala, but Kotlin code may be mixed with Java code in the same module. Using IntelliJ for editing and Gradle for Building, you can have Kotlin source files along with Java files in your project. Using Kotlin that way is no different from using any library (besides the fact that you have to learn a different syntax).
- Apply recursion to lazily evaluated collections. There is a strong relationship between the trampoline implementation and laziness. The trampoline is, in fact, a lazy computation. The trampoline can't be used for right-folding a list. However, under some conditions, a lazy-list, may be right-folded without any problem as I described in chapter 9 of my book due to the fact that no actual computation occurs. It will still blow the stack if the full lazy list is eventually evaluated. But often, it will not be the case because the number of elements will have been reduced before the data is evaluated.
It's a tiny ad only because the water is so cold.
a bit of art, as a gift, that will fit in a stocking