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-1) and 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 Trampolining[Int] and Trampolining[Int]?

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 flatMap and 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 flatMap and map functionality.

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 Trampolining[A]
• Each return value in the original function should be wrap in Return
• We want to Suspense the 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-1) and fib(n-2), will be wrapped in the FlatMap.

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 Suspense under 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 a.

Running through the Code

Let’s execute our code with fibTailRef(5) and walk through what happened internally.

When calling 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 FlatMap - Suspense case:

It will execute a FlatMap(a(), f). Therefore it will execute the a():

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 Return or 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(1) and Return(0). Then, it does the same with the inner function f.

This structure has the same form as our call stack, except it is created in the Heap.

Why trampoline?

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 run and fibWithRef, like a trampoline.

Conclusion

The 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:

• Stackless Scala with Free Monads
• Recursion and Trampolines in Scala · GitHub
• How Trampoline Works in Scala
• Trampolining and stack safety in Scala by Oleksii Avramenko

Like this Article?

Sign up for my newsletter to get notified for new articles!