This article introduces an important concept in recursion: the tail recursion. We see what tail recursion is, and where it is used.
Let us get back to the factorial program:
def factorial(n): if n == 0: return 1 return n * factorial(n - 1)
As we saw in Part 1, the execution of this program goes like this:
factorial(4) 4 * factorial(3) 4 * 3 * factorial(2) 4 * 3 * 2 * factorial(1) 4 * 3 * 2 * 1 * factorial(0) 4 * 3 * 2 * 1 * 1 4 * 3 * 2 * 1 4 * 3 * 2 4 * 6 return 24
In this program, the multiplication with 'n' is the deferred operation (See Part 1 of this series for an introduction on deferred operations). Apart from the deferred operation, there is the recursive call to calculate
factorial(n - 1).
Since the recursive call is the last step of the function, this type of recursion is called tail recursion. The name derives from the fact that the recursive call occurs at the end of the function, and after the recursive call, there is nothing more to execute in the function.
But even then, the actual multiplication happens only during the stack pop step, i.e. after the inner recursive call is over. So, in order to evaluate
factorial(4), first it will
have to execute
factorial(3) and after that returns
6, then it will calculate
4 * 6 (this multiplication is the deferred operation) and return
24. This kind of tail recursion is called ordinary tail recursion.
Ordinary tail recursion has a deferred operation and a recursive call. The above implementation of the factorial is ordinary tail recursion because it has a deferred operation.
Pure tail recursion has no deferred operation, it only has a recursive call. Take a look at this implementation of factorial:
def factorial(n): return factorial_acc(1, n) def factorial_acc(acc, n): if (n == 0): return acc return factorial_acc(n * acc, n - 1)
Let us trace the execution of this program to calculate
factorial(4) factorial_acc(1, 4) factorial_acc(4, 3) factorial_acc(12, 2) factorial_acc(24, 1) factorial_acc(24, 0) return 24
Notice the difference with the normal factorial implementation? In this version, there are no deferred operations. Instead, the multiplication is calculated immediately and passed as the first parameter to the recursive function. This parameter is known as the accumulator parameter (in case you were wondering, that is why it is called
acc, and the function is called
factorial_acc). The role of the accumulator parameter is to accumulate the result of the operations at each step. Note that this version computes the multiplication during a stack push rather than a stack pop.
Nothing is done during stack pop. When the inner function completes, the result is directly returned by the outer function. This version is pure tail recursion.