Programmers deal with recursion all the time. It’s actually quite a nice concept, but not a lot of people use it because of the mystery associated with it. To be honest, there’s no mystery as such! Sometimes, a problem is too complex to solve because it is too big. If we can break the problem down into smaller versions of itself, we may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the entire idea behind recursion. Recursive algorithms break down a problem into smaller pieces which you already know the answer to. We can solve these smaller problems by applying the same algorithm to each piece, and then combine the results. I have discussed all this in complete detail here. Now that we have talked about recursion, what exactly is the title of this blog post referring to? What exactly is tail recursion and why do we need it?
Before that, let’s talk a bit about recursion
When we talk in terms of programming, recursion is a technique involving the use of a procedure, subroutine, function, or algorithm that calls itself. But if a function keeps calling itself, it might end up in an infinite loop. So to make sure that it terminates, we need to have a termination condition so that successive repetitions are processed up to this step. Once the condition is met, the function stops calling itself. At this point, the rest of each repetition is processed from the last one all the way to the first. This is the general process of recursion.
In general, problems that are defined in terms of themselves are good candidates for recursive techniques. A common example that’s used to talk about recursion is the factorial function. The factorial of a number ‘n’ is denoted by ‘n!’. It basically describes the operation of multiplying a number by all the positive integers smaller than itself. For example, 7! = 7*6*5*4*3*2*1. If you take a closer look at this example, you will notice that 7! can be written much more concisely as 7! = 7*6!. This is a repetitive pattern. If you write a function that computes the factorial of a number, you can call the same function to compute the factorial of the previous number.
What is tail recursion?
A recursive function is tail recursive if the recursive call is the last thing executed by the function. Simple enough to understand, right? For example, the following function is tail recursive:
void printNum(int n)
{
if (n < 0) return;
cout << " " << n;
// The last executed statement is a recursive call
printNum(n-1);
}
Why do we care?
A recursive procedure calls itself to work towards a solution to the given problem. In simple implementations, this tends to blow up the stack. This happens because the nesting gets deeper and deeper, reaches the solution, then returns through all of the stack frames. This is wasteful, and it is a common complaint about recursive programming in general. As mentioned earlier, a function call is said to be tail recursive if there is nothing to do after the function returns, except returning its value. Since the current recursive instance is done executing at that point, saving its stack frame is useless. Specifically, creating a new stack frame on top of the current frame is wasteful because it’s finished.
The tail recursive functions are considered better than non-tail recursive functions because tail-recursion can be optimized by the compiler. The idea used by compilers to optimize tail-recursive functions is simple. Basically, since the recursive call is the last statement, there is nothing left to do in the current function. So saving the current function’s stack frame is of no use. The compilers can take advantage of this fact and optimize these functions accordingly.
A compiler is said to implement tail recursion if it recognizes this case and replaces the caller in place with the function that’s being called. So now, instead of nesting the stack deeper, the current stack frame is reused. This is, in effect, equivalent to a “goto” statement. It lets a programmer write recursive definitions without worrying about space inefficiency during execution. Tail recursion is then as efficient as iteration normally is. The term “tail call optimization” is sometimes used to describe the generalization of this transformation to non-recursive tail calls.
Can every non-tail-recursive function be written as a tail-recursive function to optimize it?
Consider the following function to calculate factorial of ‘n’. It is a non-tail-recursive function, although it looks like a tail recursive function at first look. If we take a closer look, we can see that the value returned by fact(n-1) is used in fact(n), so the call to fact(n-1) is not the last thing done by fact(n)
int fact(int n)
{
if (n == 0) return 1;
return n*fact(n-1);
}
The above function can be written as a tail recursive function. The idea is to use one more argument and accumulate the factorial value in second argument. When ‘n’ reaches 0, return the accumulated value.
int factTR(int n, int a)
{
if (n == 0) return a;
return factTR(n-1, n*a);
}
// A wrapper over factTR
unsigned int fact(unsigned int n)
{
return factTR(n, 1);
}
As we can see, we managed to convert a non-tail-recursive function into a tail-recursive function. If we have a compiler that implements tail call optimization, we are good to go!
Perpetual Enigma 