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.

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.

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. |

C Primer Plus (5th Edition)

ISBN: 0672326965

EAN: 2147483647

EAN: 2147483647

Year: 2000

Pages: 286

Pages: 286

Authors: Stephen Prata

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net