Putting Recursion to Work: Calculating n Factorial

---

Our previous recursive methods have not presented us with any useful abilities. Before we look at examples of how we can exploit the mechanisms demonstrated so far to solve computational problems, let's line up the main ideas of how recursion can help us solve a problem.

Recursion is suited to solve problems that can be solved by repeatedly dividing a task into two smaller (or simpler) but similar problems. When the task has been divided a number of times (through recursive calls), a base case (see earlier) task will present itself and break the chain of recursive calls. The recursive method only knows the direct answer to the base case, but by combining the partial answers to the subtasks (held by pending method calls) with the answer to the base case (all being combined while the pending method calls returns), the full answer to the original problem emerges, and a total answer can be provided by the initial method instance of the recursive method. This is an exotic series of events that is probably best explained through examples.

The first recursive method presented in the following example has the ability to calculate the factorial of a number.

Note

The ability to calculate the factorial of a number is not confined to recursive methods. Any problem that can be solved recursively also can be solved iteratively. This fact is discussed later in the chapter.

The factorial of a number n is an important mathematical function written as n! (and called n factorial) and is defined as follows:

where n must be a positive integer or zero, and where 0! is defined to be equal to 1.

Examples: 4 factorial can be written as

1 factorial is

and 0 factorial is

To see why n! can be found recursively, observe that the following is true:

This becomes evident if we write:

From this observation, we see that the factorial can be calculated by being separated into two sub-problems where one part is known (the n on the left of the multiplication sign) and the other ((n-1)!) is a smaller version of the original problem n!. We also notice that n-1 can be used similarly to (level-1) in line 17 of Listing 23.2, so it allows us to move closer to a base case that can be calculated directly as (0! = 1). Listing 23.3 presents the method Factorial, a recursive method for calculating factorials based on the observations we've just made.

Listing 23.3 Factorial.cs

01: using System; 02: 03: class MyMath 04: { 05:     public static long Factorial (long number) 06:     { 07:         if (number == 0) 08:             return 1; 09:         else 10:             return (number * Factorial (number - 1)); 11:     } 12: } 13: 14: class TestFactorial 15: { 16:     public static void Main() 17:     { 18:         Console.WriteLine("4 factorial is { 0} ", MyMath.Factorial(4)); 19:     } 20: } 4 factorial is 24 

The Factorial method's base case is when number is equal to zero, because we know that 0! is equal to 1. This is reflected in lines 7 and 8 that collectively say that if number is equal to 0, return 1. If number is larger than zero, we can use our earlier definition for factorial.

The Factorial method returns the value for a factorial, so we can write the earlier definition as follows:

 number * Factorial (number 1) 

as shown in line 10. The last part of line 10 is a recursive call. Observe that (number-1) makes every recursive call to Factorial get closer to the base case. If this was not the case, the method would (attempt to) perform an infinite amount of recursive calls.

In our test run, we asked the Factorial method to calculate 4 factorial. The resulting flow of execution has been illustrated in Figure 23.3. The Factorial keeps calling itself until number reaches the base case, which happens when five Factorial method instances have been generated. The last Factorial method instance returns 1 (because number is 0) to the previous pending Factorial method, where this value (1) is substituted for Factorial (1-1) to calculate 1 * Factorial (1-1) = 1 * 1 = 1. The result of this calculation (1) is again returned to the previous pending Factorial method where it is substituted for Factorial (2-1) to calculate 2 * Factorial (2-1) = 2 * 1 = 2. This series of events keeps repeating until the topmost Factorial method instance is reached. At this level, we now know that the value of Factorial (4-1) is 6, because this value has been returned from the underlying mass of Factorial method instances. This finally allows us to calculate 4! as 4 * 6 = 24, which is returned to the Main method from where the initial call to Factorial was made.

Figure 23.3. Five Factorial instances.

Common Ingredients Found in Correct Recursive Methods

It is hard to provide a simple recipe for writing correct recursive methods, but most successful recursive methods contain the following ingredients:

• A branching statement, such as an if-else statement or a switch statement.

• One or more of the branches of the branching statement contains recursive calls that must bring the generated method instance closer to the base case.

• One or more of the branches of the branching statement contains base cases that do not contain recursive calls but simple return statements instead that might or might not return a value.

Advanced programmers often use a mathematical technique called mathematical induction to construct recursive methods and to prove that they are correct. However, this technique is beyond the scope of this book.

---