The Tale of ‘Tail Recursion’

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

Recursions are really cool and highly expressive. For example, consider this factorial function:

But if I increase the size of input, the code will blow up.

Recursions don’t scale very well for large input sizes. And in practical way, I want to use recursions when the problem size is complex and big. So, it kind of defeats the purpose. You can't use it when you need it the most.

This is where a fairly interesting set of techniques come in.

Distinction between a procedure and process.

Procedure: The code we write.

Process: The code that runs.

So essentially, the idea is to write a piece of code that gets transformed into an optimized one when we run it.

We can write such code in the following ways:

• We can write code in an iterative procedure and run it as an iterative process. But it is not expressive.

• And we can write code in a recursive procedure and run it as a recursive process. Unfortunately, it does not scale. When our input size gets big, it fails.

• Another technique is to use some compiler magic if we can to write code as a recursive procedure and transform it into an iterative process under the covers. An implementation with this property is called tail-recursive.

So, now it is working and the stack didn’t blow up this time. In order to see how it works, let's analyze the stack trace of both functions:

In a normal recursive function, we are five levels deep. Now let’s see the stack trace of tail-recursive code.

Notice the difference in output. The point here is that there is only one level of stack. Structurally, we didn’t reduce number of recursive calls. We are still going through five recursions. The reason we have only one level of stack is that the compiler was able to optimize it. Very quietly under the covers, the compiler modified this recursion into a simple iteration.

I hope this has been helpful!