Chapter 15

What does the following code do? 1 public int mystery( int a, int b ) 2 { 3 if ( b == 1 ) 4 return a; 5 else 6 return a + mystery( a, b - 1 ); 7 } // end method mystery

Find the error(s) in the following recursive method, and explain how to correct it (them). This method should find the sum of the values from 0 to n. 1 public int sum( int n ) 2 { 3 if ( n == 0 ) 4 return 0; 5 else 6 return n + sum( n ); 7 } // end method sum

(Recursive power Method) Write a recursive method power( base, exponent ) that, when called, returns base exponent For example, power( 3,4 ) = 3 * 3 * 3 * 3. Assume that exponent is an integer greater than or equal to 1. [Hint: The recursion step should use the relationship base exponent = base · base exponent – 1 and the terminating condition occurs when exponent is equal to 1, because base1 = base Incorporate this method into a program that enables the user to enter the base and exponent.]

What does the following program do? 1 // Exercise 15.12 Solution: MysteryClass.java 2 3 public class MysteryClass 4 { 5 public int mystery( int array2[], int size ) 6 { 7 if ( size == 1 ) 8 return array2[ 0 ]; 9 else 10 return array2[ size - 1 ] + mystery( array2, size - 1 ); 11 } // end method mystery 12 } // end class MysteryClass 1 // Exercise 15.12 Solution: MysteryTest.java 2 3 public class MysteryTest 4 { 5 public static void main( String args[] ) 6 { 7 MysteryClass mysteryObject = new MysteryClass(); 8 9 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 10 11 int result = mysteryObject.mystery( array, array.length ); 12 13 System.out.printf( "Result is: %d\n", result ); 14 } // end method main 15 } // end class MysteryTest

What does the following program do? 1 // Exercise 15.13 Solution: SomeClass.java 2 3 public class SomeClass 4 { 5 public String someMethod( 6 int array2[], int x, String output ) 7 { 8 if ( x < array2.length ) 9 return String.format( 10 "%s%d ", someMethod( array2, x + 1 ), array2[ x ] ); 11 else 12 return ""; 13 } // end method someMethod 14 } // end class SomeClass

(Palindromes) A palindrome is a string that is spelled the same way forward and backward. Some examples of palindromes are “radar,” “able was i ere i saw elba” and (if spaces are ignored) “a man a plan a canal panama.” Write a recursive method testPalindrome that returns boolean value true if the string stored in the array is a palindrome and false otherwise. The method should ignore spaces and punctuation in the string.

(Eight Queens) A puzzler for chess buffs is the Eight Queens problem, which asks the following: Is it possible to place eight queens on an empty chessboard so that no queen is “attacking” any other (i.e., no two queens are in the same row, in the same column or along the same diagonal)? For instance, if a queen is placed in the upper-left corner of the board, no other queens could be placed in any of the marked squares shown in Fig. 15.23. Solve the problem recursively. [Hint: Your solution should begin with the first column and look for a location in that column where a queen can be placed—initially, place the queen in the first row. The solution should then recursively search the remaining columns. In the first few columns, there will be several locations where a queen may be placed. Take the first available location. If a column is reached with no possible location for a queen, the program should return to the previous column, and move the queen in that column to a new row. This continuous backing up and trying new alternatives is an example of recursive back-tracking.]

(Print an Array Backward) Write a recursive method stringReverse that takes a character array containing a string as an argument and prints the string backward. [Hint: Use String method toCharArray, which takes no arguments, to get a char array containing the characters in the String.]

(Find the Minimum Value in an Array) Write a recursive method recursiveMinimum that determines the smallest element in an array of integers. The method should return when it receives an array of one element.

(Time to Calculate Fibonacci Numbers) Enhance the Fibonacci program of Fig. 15.5 so that it calculates the approximate amount of time required to perform the calculation and the number of calls made to the recursive method. For this purpose, call static System method current- TimeMillis, which takes no arguments and returns the computer’s current time in milliseconds. Call this method twice—once before and once after the call to fibonacci. Save each value and cal- culate the difference in the times to determine how many milliseconds were required to perform the calculation. Then, add a variable to the FibonacciCalculator class, and use this variable to deter- mine the number of calls made to method fibonacci. Display your results.