Professional Web Hosting - Comcast Web Hosting Java Blog

288 Methods Chapter 6 Chapter Recursion examples and exercises Linked-list insert Linked-list delete Search a linked list Print a linked list backward Binary-tree insert Preorder traversal of a binary tree Inorder traversal of a binary tree Postorder traversal of a binary tree Fig. 6.15Summary of recursion examples and exercises in this text (part 2 of 2). g. 6.15 Let us reconsider some observations we make repeatedly throughout this book. Good software engineering is important. High performance is often important. Unfortunately, these goals are often at odds with one another. Good software engineering is key to making more manageable the task of developing larger and more complex software systems. High performance in these systems is key to realizing the systems of the future, which will place ever greater computing demands on hardware. Where do methods fit in here? Software Engineering Observation 6.11 Modularizing programs in a neat, hierarchical manner promotes good software engineering. But it has a price. Performance Tip 6.5 A heavily modularized program as compared with a monolithic (i.e., one-piece) program without methods makes potentially large numbers of method calls, which consume execution time and space on a computer s processor(s). But monolithic programs are difficult to program, test, debug, maintain and evolve. So modularize your programs judiciously, always keeping in mind the delicate balance between performance and good software engineering. 6.15 Method Overloading Java enables several methods of the same name to be defined, as long as the methods have different sets of parameters (based on the number of parameters, the types of the parameters and the order of the parameters). This characteristic is called method overloading. When an overloaded method is called, the Java compiler selects the proper method by examining the number, types and order of the arguments in the call. Method overloading is commonly used to create several methods with the same name that perform similar tasks, but on different data types. Good Programming Practice 6.9 Overloading methods that perform closely related tasks can make programs more readable and understandable. Figure 6.16 uses overloaded method square to calculate the square of an int and the square of a double. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 287 memory space. Iteration normally occurs within a method, so the overhead of repeated method calls and extra memory assignment is omitted. So why choose recursion? Software Engineering Observation 6.10 Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally preferred over an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. Often, a recursive approach can be implemented with few lines of code and a corresponding iterative approach may take large amounts of code. Another reason to choose a recursive solution is that an iterative solution may not be apparent. Performance Tip 6.4 Avoid using recursion in situations requiring performance. Recursive calls take time and consume additional memory. Common Programming Error 6.16 Accidentally having a nonrecursive method call itself either directly or indirectly through another method can cause infinite recursion. Most programming textbooks introduce recursion much later than we have done here. We feel that recursion is a sufficiently rich and complex topic that it is better to introduce it earlier and spread examples of it over the remainder of the text. Figure 6.15 summarizes the recursion examples and exercises in this text. Chapter Recursion examples and exercises 6 Factorial method Fibonacci method Greatest common divisor Sum of two integers Multiply two integers Raising an integer to an integer power Towers of Hanoi Visualizing recursion 7 Sum the elements of an array Print an array Print an array backward Check if a string is a palindrome Minimum value in an array Selection sort Eight Queens Linear search Binary search Quicksort Maze traversal 10 Printing a string input at the keyboard backward Fig. 6.15Summary of recursion examples and exercises in this text (part 1 of 2). g. 6.15 Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

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

Chapter 6 Methods 285 Figure 6.14 shows how method fibonaccievaluates fibonacci(3). In the figure, f is an abbreviation for fibonacci. Figure 6.14 raises some interesting issues about the order in which Java compilers evaluate the operands of operators. This issue is different than the order in which operators are applied to their operands, namely the order dictated by the rules of operator precedence. From Fig. 6.14, it appears that while f(3)is being evaluated, two recursive calls will be made, namely f(2)and f(1). But in what order will these calls be made? Most programmers assume that the operands will be evaluated left to right. In Java, this assumption is true. The C and C++ languages (on which many of Java s features are based) do not specify the order in which the operands of most operators (including +) are evaluated. Therefore, the programmer can make no assumption in those languages about the order in which the calls in this example execute. The calls could, in fact, execute f(2)first andf(1)second, or the calls could be executed in the reverse order: f(1), then f(2). In this program and in most other programs, it turns out that the final result would be the same for either case. But in some programs, the evaluation of an operand may have side effects that could affect the final result of the expression. The Java language specifies that the order of evaluation of the operands is from left to right. Thus, the method calls are in fact f(2)first andf(1)second. Good Programming Practice 6.8 Do not write expressions that depend on the order of evaluation of the operands of an operator. Use of such expressions often results in programs that are difficult to read, debug, modify and maintain. A word of caution is in order about recursive programs like the one we use here to generate Fibonacci numbers. Each invocation of the fibonaccimethod that does not match one of the base cases (i.e., 0 or 1) results in two more recursive calls to the fibonacci method. This set of recursive calls rapidly gets out of hand. Calculating the Fibonacci value of 20 using the program in Fig. 6.13 requires 21,891 calls to the fibonaccimethod; calculating the Fibonacci value of 30 requires 2,692,537 calls to the fibonaccimethod. f( 3 ) f( 1 )f( 2 ) f( 1 ) f( 0 ) return 1 return 1 return 0 return + +return Fig. 6.14 Set of recursive calls to method fibonacci(fin this diagram). Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

284 Methods Chapter 6 Fig. 6.13 Recursively generating Fibonacci numbers (part 3 of 3). The call to fibonacci(line 59) from actionPerformed is not a recursive call, but all subsequent calls to fibonacci performed from the body of fibonacci are recursive. Each time fibonacci is invoked, it immediately tests for the base case n equal to 0 or 1. If this condition is true, fibonacci returns n (fibonacci(0) is 0, and fibonacci(1) is 1). Interestingly, if n is greater than 1, the recursion step generates two recursive calls, each for a slightly simpler problem than the original call to fibonacci. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 283 40 // create numberField, make it uneditable 41 // and attach it to content pane 42 resultField = new JTextField( 15 ); 43 resultField.setEditable( false ); 44 container.add( resultField ); 45 46 } // end method init 47 48 // obtain user input and call method fibonacci 49 public void actionPerformed( ActionEvent e ) 50 { 51 long number, fibonacciValue; 52 53 // obtain user s input and conver to long 54 number = Long.parseLong( numberField.getText() ); 55 56 showStatus( “Calculating …” ); 57 58 // calculate fibonacci value for number user input 59 fibonacciValue = fibonacci( number ); 60 61 // indicate processing complete and display result 62 showStatus( “Done.” ); 63 resultField.setText( Long.toString( fibonacciValue ) ); 64 65 } // end method actionPerformed 66 67 // Recursive definition of method fibonacci 68 public long fibonacci( long n ) 69 { 70 // base case 71 if ( n == 0 || n == 1 ) 72 return n; 73 74 // recursive step 75 else 76 return fibonacci( n -1 ) + fibonacci( n -2 ); 77 78 } // end method fibonacci 79 80 } // end class FibonacciTest Fig. 6.13 Recursively generating Fibonacci numbers (part 2 of 3). Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

282 Methods Chapter 6 The event handling in this example is similar to the event handling of the Craps applet in Fig. 6.9. Line 34 specifies that this applet should listen for events from the JTextFieldnumberField. Remember, the thiskeyword enables the applet to refer to itself. So, in line 34, the applet is telling numberFieldthat the applet should be notified (with a call to the applet s actionPerformedmethod) when an action event occurs in the numberField. In this example, the user presses the Enter key while typing in the numberField to generate the action event. A message is then sent to the applet (i.e., a method actionPerformed is called on the applet) indicating that the user of the program has interacted with one of the program s GUI components (numberField). Remember that the statement to register the applet as the numberField s listener will compile only if the applet class also implements ActionListener(line l2). 1 // Fig. 6.13: FibonacciTest.java 2 // Recursive fibonacci method 3 4 // Java core packages 5 import java.awt.*; 6 import java.awt.event.*; 7 8 // Java extension packages 9 import javax.swing.*; 10 11 public class FibonacciTest extends JApplet 12 implements ActionListener { 13 14 JLabel numberLabel, resultLabel; 15 JTextField numberField, resultField; 16 17 // set up applet s GUI 18 public void init() 19 { 20 // obtain content pane and set its layout to FlowLayout 21 Container container = getContentPane(); 22 container.setLayout( new FlowLayout() ); 23 24 // create numberLabel and attach it to content pane 25 numberLabel = 26 new JLabel( “Enter an integer and press Enter” ); 27 container.add( numberLabel ); 28 29 // create numberField and attach it to content pane 30 numberField = new JTextField( 10 ); 31 container.add( numberField ); 32 33 // register this applet as numberField s ActionListener 34 numberField.addActionListener( this ); 35 36 // create resultLabel and attach it to content pane 37 resultLabel = new JLabel( “Fibonacci value is” ); 38 container.add( resultLabel ); 39 Fig. 6.13 Recursively generating Fibonacci numbers (part 1 of 3). Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 281 factorial method produces large values so quickly that even long does not help us print many factorial values before the values exceed the size that can be stored in a long variable. We explore in the exercises the fact that float and double may ultimately be needed by users desiring to calculate factorials of larger numbers. This situation points to a weakness in most programming languages, namely, that the languages are not easily extended to handle the unique requirements of various applications. As we will see in Chapter 9, Object-Oriented Programming, Java is an extensible language that allows us to create arbitrarily large integers if we wish. In fact, package java.math provides two classes BigInteger and BigDecimal explicitly for mathematical calculations of arbitrary precision that cannot be represented with Java s primitive data types. Common Programming Error 6.15 Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case will cause infinite recursion, eventually exhausting memory. This error is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution. 6.13 Example Using Recursion: The Fibonacci Series The Fibonacci series, 0,1, 1, 2, 3, 5, 8, 13,21, begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers. The series occurs in nature and, in particular, describes a form of spiral. The ratio of successive Fibonacci numbers converges on a constant value of 1.618 . This number, too, repeatedly occurs in nature and has been called the golden ratio, or the golden mean. Humans tend to find the golden mean aesthetically pleasing. Architects often design windows, rooms and buildings whose length and width are in the ratio of the golden mean. Postcards are often designed with a golden-mean length/width ratio. The Fibonacci series may be defined recursively as follows: fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(n) = fibonacci(n 1) + fibonacci(n 2) Note that there are two base cases for the Fibonacci calculation: fibonacci(0) is defined to be 0, and fibonacci(1) is defined to be 1. The applet of Fig. 6.13 calculates the ith Fibonacci number recursively, using method fibonacci (lines 68 78). The applet enables the user to input an integer in a JTextField. The value input indicates the ith Fibonacci number to calculate. When the user presses the Enter key, method actionPerformed executes in response to the user interface event and calls method fibonacci to calculate the specified Fibonacci number. Fibonacci numbers tend to become large quickly. Therefore, we use data type longas the parameter type and the return type of fibonacci. In Fig. 6.13, the screen captures show the results of calculating several Fibonacci numbers. Once again, method init of this applet creates the GUI components and attaches them to the applet s content pane. The layout manager for the content pane is set to Flow- Layout at line 22. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

280 Methods Chapter 6 7 // Java extension packages 8 import javax.swing.*; 9 10 public class FactorialTest extends JApplet { 11 JTextArea outputArea; 12 13 // initialize applet by creating GUI and calculating factorials 14 public void init() 15 { 16 outputArea = new JTextArea(); 17 18 Container container = getContentPane(); 19 container.add( outputArea ); 20 21 // calculate the factorials of 0 through 10 22 for ( long counter = 0; counter <= 10; counter++ ) 23 outputArea.append( counter + “! = ” + 24 factorial( counter ) + “n” ); 25 26 } // end method init 27 28 // Recursive definition of method factorial 29 public long factorial( long number ) 30 { 31 // base case 32 if ( number <= 1 ) 33 return 1; 34 35 // recursive step 36 else 37 return number * factorial( number -1 ); 38 39 } // end method factorial 40 41 } // end class FactorialTest Fig. 6.12Calculating factorials with a recursive method (part 2 of 2). Fig. 6.12 Method factorial(line 29) receives a parameter of type longand returns a result of type long. As can be seen in Fig. 6.12, factorial values become large quickly. We chose data type longso the program can calculate factorials greater than 20!. Unfortunately, the Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 279 A recursive definition of the factorial method is arrived at by observing the following relationship: n! = n (n -1)! For example, 5! is clearly equal to 5 * 4!, as is shown by the following equations: 5!= 5 4 3 2 1 5! = 5 (4 3 2 1) 5! = 5 (4!) The evaluation of 5! would proceed as shown in Fig. 6.11. Figure 6.11 (a) shows how the succession of recursive calls proceeds until 1! is evaluated to be 1, which terminates the recursion. Figure 6.11 (b) shows the values returned from each recursive call to its caller until the final value is calculated and returned. Figure 6.12 uses recursion to calculate and print the factorials of the integers from 0 to 10. (The choice of the data type long will be explained momentarily.) The recursive method factorial(lines 29 39) first tests to determine whether a terminating condition (line 32) is true. If numberis less than or equal to 1(the base case), factorialreturns 1, no further recursion is necessary and the method returns. If numberis greater than 1, line 37 expresses the problem as the product of number and a recursive call to factorialevaluating the factorial of number-1. Note that factorial(number-1)is a slightly simpler problem than the original calculation factorial(number). 5! 5 * 4! 4 * 3! 3 * 2! 2 * 1! 1 5! 5 * 4! 4 * 3! 3 * 2! 2 * 1! 1 Final value = 120 5! = 5 * 24 = 120 is returned 4! = 4 * 6 = 24 is returned 2! = 2 * 1 = 2 is returned 3! = 3 * 2 = 6 is returned 1 returned (a) Procession of recursive calls. (b) Values returned from each recursive call. Fig. 6.11 Recursive evaluation of 5!. 1 // Fig. 6.12: FactorialTest.java 2 // Recursive factorial method 3 4 // Java core packages 5 import java.awt.*; 6 Fig. 6.12Calculating factorials with a recursive method (part 1 of 2). Fig. 6.12 Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01