286 Methods (Web domain) Chapter 6 As you try calculate
286 Methods Chapter 6 As you try calculate larger Fibonacci values, you will notice that each consecutive Fibonacci number you ask the applet to calculate results in a substantial increase in calculation time and number of calls to the fibonacci method. For example, the Fibonacci value of 31 requires 4,356,617 calls, and the Fibonacci value of 32 requires 7,049,155 calls. As you can see, the number of calls to fibonacci is increasing quickly 1,664,080 additional calls between Fibonacci values of 30 and 31 and 2,692,538 additional calls between Fibonacci values of 31 and 32. This difference in number of calls made between Fibonacci values of 31 and 32 is more than 1.5 times the number of calls for Fibonacci values between 30 and 31. Problems of this nature humble even the world s most powerful computers! In the field of complexity theory, computer scientists study how hard algorithms work to complete their tasks. Complexity issues are discussed in detail in the upper-level computer science curriculum course generally called Algorithms. Performance Tip 6.3 Avoid Fibonacci-style recursive programs, which result in an exponential explosion of calls. Testing and Debugging Tip 6.3 Try enhancing the Fibonacci program of Fig. 6.13 such that it calculates the approximate amount of time required to perform the calculation. For this purpose, call static System method getCurrentTimeMillis, which takes no arguments and returns the computer s current time in milliseconds. Call this method twice once before the call to fibonacci and once after the call to fibonacci. Save each of these values and calculate the difference in the times to determine how many milliseconds were required to perform the calculation. Display this result. 6.14 Recursion vs. Iteration In the previous sections, we studied two methods that can easily be implemented either recursively or iteratively. In this section,we compare the two approaches and discuss why the programmer might choose one approach over the other in a particular situation. Both iteration and recursion are based on a control structure: Iteration uses a repetition structure (such as for, while or do/while); recursion uses a selection structure (such as if, if/else or switch). Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated method calls. Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized. Iteration with counter-controlled repetition and recursion each gradually approach termination: Iteration keeps modifying a counter until the counter assumes a value that makes the loop- continuation condition fail; recursion keeps producing simpler versions of the original problem until the base case is reached. Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem each time in a manner that converges on the base case. Recursion has many negatives. It repeatedly invokes the mechanism and, consequently the overhead, of method calls. This repetition can be expensive in terms of both processor time and memory space. Each recursive call causes another copy of the method (actually, only the method s variables) to be created; this set of copies can consume considerable Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01