Java Reference
In-Depth Information
So, the computer time required to generate 2 64 moves is:
2 64 1 : 6 10 19 ¼ 1 : 6 10 16 10 3 ¼ð 3 : 2 10 16 Þ 500
Thus, it would take about 500 years for the computer to generate 2 64 moves at the rate of
1 billion moves per second.
Recursion or Iteration?
In Chapter 5, we designed a program to determine a desired Fibonacci number. That
program used a loop to perform the calculation. In other words, the programs in Chapter
5 used an iterative control structure to repeat a set of statements. More formally, iterative
control structures use a looping structure, such as while , for ,or do ... while ,to
repeat a set of statements. In Example 13-2, we designed a recursive method to calculate a
Fibonacci number. From the examples in this chapter, it follows that in recursion, a set of
statements is repeated by having the method call itself. Moreover, a selection control
structure is used to control the repeated calls in recursion.
Similarly, in Chapter 9, we used an iterative control structure (a for loop) to determine
the largest element in a list. In this chapter, we used recursion to determine the largest
element in a list. In addition, this chapter began by designing a recursive method to find
the factorial of a nonnegative integer. Using an iterative control structure, we can also
write an algorithm to find the factorial of a nonnegative integer. The only reason we gave
a recursive solution to a factorial problem is to illustrate how recursion works.
Often there are two ways to solve a particular problem—recursion or iteration. The obvious
question is, Which method is better? There is no simple answer. In addition to the nature of
the problem, the other key factor in determining the best solution method is efficiency.
When we traced the execution of the program in Example 7-11 (Chapter 7), we saw that
whenever a method is called, memory space for its formal parameters and (automatic) local
variables is allocated. When the method terminates, that memory space is then deallocated.
In this chapter, while tracing the execution of recursive methods, we saw that every
(recursive) call also had its own set of parameters and local variables. That is, every
(recursive) call required that the system allocate memory space for its formal parameters
and local variables, and then deallocate the memory space when the method exited. Thus,
overhead is associated with executing a (recursive) method, both in terms of memory
space and computer time. Therefore, a recursive method executes more slowly than its
iterative counterpart. On slower computers, especially those with limited memory space,
the (slow) execution of a recursive method would be noticeable.
Today's computers, however, are fast and have ample memory. Therefore, the execution
of a recursive method is not so noticeable. Keeping in mind the power of today's
computers, the choice between iteration or recursion depends on the nature of the
 
Search WWH ::




Custom Search