Recursion and Iteration

---

Iteration uses one of the language constructs for, while, or do-while, as discussed in Chapter 9, "Flow of Control Part II: Iteration Statements." Any computational problem that can be solved by using recursion also can be solved solely through iteration. For example, the Factorial method contained in Listing 23.4 uses a for loop construct to calculate the factorial and, thereby, uses iteration instead of recursion as in Listing 23.3.

Listing 23.4 IterativeFactorial.cs

01: using System; 02: 03: class Math 04: { 05:     public static long Factorial(long number) 06:     { 07:         long factorial = 1; 08: 09:         for(long i = number; i >= 1; i--) 10:         { 11:             factorial *= i; 12:         } 13:         return factorial; 14:     } 15: } 16: 17: class Tester 18: { 19:     public static void Main() 20:     { 21:         Console.WriteLine("4! = { 0} ", Math.Factorial(4)); 22:     } 23: } 4! = 24 

We want to calculate the factorial of number defined as Factorial's formal parameter in line 5. The counter i defined in line 9 will initially have the value number. Line 11 is repeatedly executed until i is less than 1. Every time line 11 is executed, i is multiplied by factorial and decremented by one, so by the time i is one, factorial contains the value number!.

Both recursion and iteration use repetition. Recursion involves repeated method calls that gradually bring method instances closer to a base case. This process stops when the base case is reached. Iteration often entails counters that are incremented or decremented until the loop condition becomes false.

Whereas iteration often involves just one method instance, recursion, as we have seen previously, relies on the creation of many method instances (and their associated local variable values) to solve a problem. It is costly for the runtime to keep track of and store method instances both in terms of memory and CPU time. Consequently, iteration is usually more efficient than recursion.

If all computational problems can be solved with iteration, and iteration is more efficient than recursion, why then ever use recursion? Sometimes a recursive solution is more apparent and elegant as well as being simpler, cleaner to write, and easier to understand than an iterative solution. This is usually the case when the computational problem can naturally be expressed in recursive terms.

The next section shows an example of an iterative solution that can be implemented by using recursion.

---