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 they are highly expressive. For example consider factorial function:

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

Recursions don’t scale very well for large input sizes. And in practical way, when i use the recursion when problem size is complex and big. So, its kind of defeat when you need it most you can’t use it.

This is where fairly set of interesting 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 optimized one when we run it.

We can write code in following ways:

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

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

Another technique, use some compiler magic if we can, To write code as recursive procedure and gets transformed into iterative process under the covers.

An implementation with this property is called tail-recursive.

So, now it is working and stack didn’t blow up this time.

In order to see how it is working, lets analyze the stack trace of both functions:

In normal recursive function, we are five level deep in stack. 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 is why we have only one level of stack, Compiler was able to optimize it. Very quietly under the covers, compiler modified this recursion into simple iteration.

Hope that this blog is helpful for you.

Reference:

1. Structure and interpretation of computer programs by Gerald Jay Sussman and Hal Abelson