Tail Recursion

A tail recursive method is efficient for reducing stack size. A recursive method is said to be tail recursive if there are no pending operations to be performed on return from a recursive call, as illustrated in Figure below (a). However, method B in Figure below (b) is not tail recursive because there are pending operations after a method call is returned.

For example, the recursive isPalindrome method (lines 9–16) in RecursivePalindrome.java is tail recursive because there are no pending operations after recursively invoking isPalindrome in line 15. However, the recursive factorial method (lines 17–22) in ComputeFactorial.java is not tail recursive, because there is a pending operation, namely multiplication, to be performed on return from each recursive call.

Tail recursion is desirable: because the method ends when the last recursive call ends, there is no need to store the intermediate calls in the stack. Compilers can optimize tail recursion to reduce stack size.

A nontail-recursive method can often be converted to a tail-recursive method by using auxiliary parameters. These parameters are used to contain the result. The idea is to incorporate the pending operations into the auxiliary parameters in such a way that the recursive call no longer has a pending operation. You can define a new auxiliary recursive method with the auxiliary parameters. This method may overload the original method with the same name but a different signature. For example, the factorial method in ComputeFactorial.java is written in a tail-recursive way in the code below.

The first factorial method (line 5) simply invokes the second auxiliary method (line 6). The second method contains an auxiliary parameter result that stores the result for the factorial of n. This method is invoked recursively in line 14. There is no pending operation after a call is returned. The final result is returned in line 12, which is also the return value from invoking factorial(n, 1) in line 6.