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.

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.

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