Wrapping my head around Tail Recursion and TCO
I’ve recently been going down the functional programming rabbit hole.
One FP concept which has been pretty fascinating to learn about is tail recursion, along with the optimisations it can provide (given some requirements).
It’s also a surprisingly nice way to get exposed to a bunch of different concepts, including the stack, which in turn requires you to think about memory, etc.
In this post I’ll attempt to explain it from first principles, and then go over an actual implementation of tail recursion in OCaml.
The first quest on the agenda is recursion.
Recursion, Computer Memory, and You
A recursive function is a function which call itself in its own function body.
There is a base case (essentially the condition to make the function terminate), and the recursive case: the function call. The issue with recursion is that if your function doesn’t hit its base case, i.e. doesn’t terminate, you can cause your computer some problems.
So, what exactly does this mean?
Whenever you run a program on your computer, your OS allocates it some memory. As a developer, this is given to you as a region of virtual memory which is an abstraction over your actual RAM.
This virtual memory has different areas, one of which is called the stack. This is just an area of memory on your computer basically dedicated to one thing: handling function calls. Whenever your program runs a function, its local data is added to the stack in something called a stack frame.
If your recursive function doesn’t terminate, you can run out of stack memory and get a “stack overflow” error.
Tail recursion is a method or writing recursive functions in such a way that to avoid certain stack overflow errors.
Introducing Tail Recursion
A typical recursive function for calculating factorials in OCaml looks like this:
let rec factorial n =
if n = 0 then 1
else n * factorial (n - 1)
It is relatively straight-forward:
- You define a recursive function, which takes one argument (n)
- If the number passed in is 0, we just return 1
- If the number isn’t 0, we call factorial again (going down by one each time) and multiply it by the previous number
With very large numbers, it’s possible for this to run out of stack memory. Luckily for me, some very clever people worked out an optimisation for this.
If you think about it, the issue is that the function calls stack up (excuse the pun) and none of them ever “pop”, so they just continue growing. So if you can find a way around this and make it so each recursive function call actually terminates, you’ll pretty much never run out of stack space. The way to do this is by making sure the recursive call is always the last thing that happens.
This might look like the case with the above function, but the else statement calls the factorial function, and the n * part has to wait until all of the function chains unravel.
To make it tail recursive, you have to move this multiplication part inside of the function call. This is typically done with the help of another function called an accumulator.
Here's what it will look like:
let rec tail_factorial acc n =
if n = 0 then acc
else tail_factorial (acc * n) (n - 1)
So the key difference here is the acc function "accumulates", i.e. keeps a running value of the multiplication before the recursive call.
What's so ingenious about this is that although recursive, it now completely eliminates this stack of recursive calls and turns it into something more akin to a "flat" for loop.
Links
A lot of my understanding of recursion and tail recursion draws on explanations presented in:
You may find the explanations there beneficial.
Thanks for reading.