Recursion is often used when we want to compute combination values and other iterative values. Having a recursion in your function can decrease the amount of code that you write in your function. However, a lot of the time, recursive calls can be hard to deal with when you have extensive input.
Let’s take an example of calling Fibonacci.
Having a recursive call of
fib(n-2) is readable. However, when we input
fib(1000000). It throws stack overflow.
In a regular recursive call, we can optimize the value by making it tail-recursive. Usually, in scala with annotation of
@tailRec to tell the compiler to static check if the current function that you wrote is tail-recursive or not.
The problem with this is that tail-recursive sometimes is hard to construct, and some function with just regular code and cannot complete tail recursion. Consider creating Fibonacci in a tail-recursive manner.
This post is inspired by the book Functional Programming in Scala by Runar Bjarnason. He tried to explain the
IO and give some examples of creating a generic tail-recursive value for the function that we construct. This kind of tail-recursive call is called trampoline.
In this article, I would like to walk through why it is called trampoline and how we construct this trampoline function, with the example of Fibonacci, to make all function tail-recursive.
The trick for making a stack-safe recursion is to move your recursion from the stack to the heap space. Basically, instead of letting the JVM run a recursion function, pushing the new frame to the pile each recursion is performed, we want to write the recursion so that, rather than the JVM, we have control of the execution.
In the above Fibonacci case, calling the
fib itself gives that execution control to the JVM. It pushes the
fib(n-1) to the call frame because we will need to calculate
fib(n-2) and evaluate that value. If we simply reify our implementation instead of calling a function, it constructs a data type.
For instance, instead of calling
fib(n-1) we can try to wrap the function into a data type
Suspense(() => Function[Int, Int]) data types that will hold this value. Essentially, we are constructing a data structure instead of calling a function.
If we want to wrap our function call with
Suspense, our return value will also need data types.
Essentially, the function call will be something like this:
We will have a
Trampolining type constructor that wraps our result value.
If we return
Trampolining on each function call, how do you actually chain those results together?
The original values recursive value for
fib function just return an
Int. To illustrate what I mean:
It works when we do
fib(n-1) + fib(n-2) because both return an
Int, and we can do an addition on it. However, if we return a
Trampolining , how can we do chain the result of
This sounds like a
map or a
flatMap if we want to sequence our computation together.
Our function will look something like this:
However, we also reify
map to construct data types instead of calling the function
f. We just want to wrap it into the data so that it can be built in the Heap.
Therefore, our data type
Trampolining will have to have
Before I explain further on how we can make this tail recursive with
Trampoloining, let’s construct what
Trampolining should look like:
The constructor will have
Return(base case, which will return a single value),
Suspense (suspending the function to execute them later), and
FlatMap (to chain operations).
We can re-write our existing recursive function in the following manner:
- If the original function returns an
A, the new function should return a
returnvalue in the original function should be wrap in
- We want to
Suspensethe recursive call so that the program doesn’t push to our stack frame
- Things that we do after the recursive call, such as the addition of
fib(n-2), will be wrapped in the
New Fibonacci Recursive Call
Our fibonnaci recursive call right now looks like this:
The Call to Tail Recursion
Now, the purpose of making this into a data constructor is to delegate the control of the program to the programmer. We then can create an interpreter to interpret this control flow.
The interpreter is where we use tail-recursive call on our program.
Let’s create our interpreter:
Note that in
FlatMap we need to wrap it with
FlatMap to call the
f function to execute that
flatMap once the function call is finished. If you just create
run(x()) like the above, it will not execute the function after getting the value of
Running through the Code
Let’s execute our code with
fibTailRef(5) and walk through what happened internally.
fibTailRef(5), it goes to the
else statement. Through substituting our code with its definition, we can get something like this:
When we execute that constructor with our interpreter,
run, it will go to the
It will execute a
FlatMap(a(), f). Therefore it will execute the
At this point, we will evaluate our function
fibTailRef(4) which gives us:
We substitute the definition of
fibTailRef(4) above to the
run method in graph 4:
At this point, the
FlatMap case is executed underneath the
FlatMap. In this case, we re-associate our function from
a.flatMap f flatMap f1 to
a.flatMap(x => f(x).flatMap(f)) so it is tail recursive. The reason for this is because
a will keep recursively going through until it hits base case
Suspense from the first two pattern match case, and it will call the
f function after.
This won’t change the result because we are leveraging the associativity of the Monad’s law.
The above, graph 5 after being called becomes like this:
Phew! It took me a while to trace through this. Hopefully, you get my point. We can recurse through the end of the value, which will have a
Return(0). Then, it does the same with the inner function
This structure has the same form as our call stack, except it is created in the Heap.
As you can see, our stack doesn’t grow and grow. We first call the
run function, which pushes it to the stack. It will then go up to
FlatMap for the first time by creating another
FlatMap construct. When all the
Suspense values pop the stack and go to the
fibWithRef(4). Then it goes to the
run function. Then, it goes again to the
fibWithRef(3). Then it goes to
run also. Until it constructs the values.
We keep jumping back and forth from
fibWithRef, like a trampoline.
Trampolining data constructors that we created works for a lot of the recursive scenario. We wrap the value of our return statement to
Trampolining. We wrap
Return data constructor on the base case value that we return on our regular recursion call. Lastly, we do
flatMap on the operation that we want to do on the values.
This has been used a lot that Cats has an Eval monad to construct values in a stack safe way. You can check out my previous post to see how we can use Eval to construct our recursive function.
If you want to see the source code, you can see them here.
Lastly, if you are interested to learn more about trampolining, here are a few reference material to know more about: