1. Recursion versus Iteration
Recursion is an alternative form of program control. It is essentially repetition without a loop.
Recursion is an alternative form of program control. It is essentially repetition without a loop control. When you use loops, you specify a loop body. The repetition of the loop body is controlled by the loop-control structure. In recursion, the function itself is called repeatedly. A selection statement must be used to control whether to call the function recursively or not.
Recursion bears substantial overhead. Each time the program calls a function, the system must assign space for all of the function’s local variables and parameters. This can consume considerable memory and requires extra time to manage the additional space.
Any problem that can be solved recursively can be solved nonrecursively with iterations. Recursion has some negative aspects: It uses too much time and too much memory. Why, then, should you use it? In some cases, using recursion enables you to specify a clear, simple solution for an inherent recursive problem that would otherwise be difficult to obtain. The Towers of Hanoi problem is such an example, which is rather difficult to solve without using recursion.
The decision whether to use recursion or iteration should be based on the nature of the problem you are trying to solve and your understanding of it. The rule of thumb is to use whichever of the two approaches can best develop an intuitive solution that naturally mirrors the problem. If an iterative solution is obvious, use it. It generally will be more efficient than the recursive option.
2. Tail Recursion
A tail recursive function is efficient for reducing stack space.
A recursive function 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 17.10a. However, function B in Figure 17.10b is not tail recursive because there are pending operations after a function call is returned.
For example, the recursive isPalindrome function (lines 5-13) in Listing 17.4 is tail recursive because there are no pending operations after recursively invoking isPalindrome in line 12. However, the recursive factorial function (lines 21-27) in Listing 17.1 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 function ends when the last recursive call ends. So there is no need to store the intermediate calls in the stack. Some compilers can optimize tail recursion to reduce stack space.
A nontail-recursive function can often be converted to a tail-recursive function 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 may define a new auxiliary recursive function with the auxiliary parameters. This function may overload the original function with the same name but a different signature. For example, the factorial function in Listing 17.1 can be written in a tail-recursive way as follows:
1 // Return the factorial for a specified number
2 int factorial(int n)
3 {
4 return factorial(n, 1); // Call auxiliary function
5 }
6
7 // Auxiliary tail-recursive function for factorial
8 int factorial(int n, int result)
9 {
10 if (n == 1)
11 return result;
12 else
13 return factorial(n – 1, n * result); // Recursive call
14 }
The first factorial function simply invokes the second auxiliary function (line 4). The second function contains an auxiliary parameter result that stores the result for factorial of n. This function is invoked recursively in line 13. There is no pending operation after a call is returned. The final result is returned in line 11, which is also the return value from invoking factorial(n, 1) in line 4.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.