Solutions to Self-Study Exercises

[Page 595 (continued)]

Solution 12.1	The output produced by mystery(0) would be 0 1 2 3 4 5 6. The output produced by mystery(100) would be 100.
Solution 12.2	The output produced by mystery(5) would be: 5 4 3, and so on. In other words, this is an infinite recursion.

Solution 12.3	Definition: twoToN(N), N >= 0 1, if N == 0 // Base case 2 * twoToN(N - 1), N > 0 // Recursive case
Solution 12.4	The function xn is known as the power function: Definition: power(X,N), N >= 0 1, if N == 0 // Base case X * power(X, N - 1), N > 0 // Recursive case
Solution 12.5	Yes, the two definitions for nested boxes are equivalent. Suppose the square starts out with a side of 20. The definition given in the exercise will also draw squares with sides of 20, 15, 10, 5.
Solution 12.6	A recursive definition for the pattern in Figure 12.3: Draw a square with side, s. Inscribe a circle with diameter, s. If s > 5, Draw a smaller version of same pattern. // Recursive case

Solution 12.7

The printString2("hello") method will print "olleh".

Solution 12.8	A definition for countDown(): /** * countDown(N) recursively prints a countdown beginning at N and ending at 1 * @ param N >= 1 * Base case: N == 0 */ void countDown(int N) { if (N == 0) // Base case System.out.println("blastoff"); else { System.out.print(N + ", "); // Recursive case countDown(N - 1); } } // countDown()
	[Page 596]
Solution 12.9	A revised definition for countDown(): /** * countDown(N) recursively prints a countdown * beginning at N, counting every other number, 10 8 6 ... * and ending at "blastoff" * @ param N >= 1 * Base case: N <= 0 */ void countDown(int N) { if (N <= 0) // Base case System.out.println("blastoff"); else { System.out.print(N + ", "); // Recursive case countDown(N - 2 ); } } // countDown()

Solution 12.10

A method to sum the numbers from 1 to N.

int sum(int N) {     if (N == 0)         return 0;     else         return N + sum(N-1); } 

Solution 12.11

A method to change each blank within a string to two blanks.

String addBlanks(String s) {   if (s.length() == 0)      return "";   else if (s.charAt(0) == ' ')      return ' ' + s.charAt(0) + addBlanks(s.substring(1));   else      return s.charAt(0) + addBlanks(s.substring(1)); } 

Solution 12.12

A method to print out all possible outcomes for a chess player playing N games. printOutcomes(str, N) will print all outcomes for the next N games given that results for previous games are stored in the string named str.

public static void printOutcomes(String str, int N){     if (N = 1){                        // Base case: win, lose, or draw one game         System.out.println(str + "W");         System.out.println(str + "L");         System.out.println(str + "D");     } else {                           // Recursive case         printOutcomes(str + "W", N - 1);         printOutcomes(str + "L", N - 1);         printOutcomes(str + "D", N - 1);     } // else } // printOutcomes() 

	[Page 597]
Solution 12.13	public static void main(String args[]) { int numbers[] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}; Searcher searcher = new Searcher(); for (int k = 0; k <= 20; k++) { int result = searcher.search(numbers, k); if (result != -1) System.out.println(k + " found at " + result); else System.out.println(k + " is not in the array "); } // for } // main()

Solution 12.14	The sort() method is used as a public interface to the recursive selectionSort() method: /** * sort(arr) sorts the int array, arr * Pre: arr is not null * Post: arr will be arranged so that arr[j] <= arr[k] * for any j < k */ public void sort(int arr[]) { selectionSort(arr, arr.length - 1); // Just call the recursive method }
Solution 12.15	An iterative version of findMax(): /** * findMax (arr,N) returns the index of the largest * value between arr[0] and arr[N], N >= 0. * Pre: 0 <= N <= arr.length -1 * Post: arr[findMax()]>= arr[k] for k between 0 and N. */ private int findMax(int arr[], int N) { int maxSoFar = 0; for (int k = 0; k <= N; k++) if (arr[k] > arr[maxSoFar]) maxSoFar = k; return maxSoFar; } // findMax()

	[Page 598]
Solution 12.16	Levels four and five of the nested boxes pattern are shown in Figure 12.34. Figure 12.34. Levels four and five of the nested boxes pattern.
Solution 12.17	The following method will reduce the length of the side by delta percent at each level of recursion. The spacing between the boxes will vary by a constantly decreasing amount. private void drawBoxes(Graphics g, int level, int locX, int locY, int side, int delta) { g.drawRect(locX, locY, side, side ); if (level > 0) { int dside = side * delta / 100; // Percent delta int newLocX = locX + dside; int newLocY = locY + dside; drawBoxes(g, level - 1, newLocX, newLocY, side - 2 * dside, delta); } } // drawBoxes()
Solution 12.18	private void drawBoxesIterative(Graphics g, int level, int locX, int locY, int side, int delta) { for (int k = level; k >= 0; k--) { g.drawRect(locX, locY, side, side ); // Draw a square locX += delta; // Calculate new location locY += delta; side -= 2 * delta; // Calculate new side length } } // drawBoxes()

	[Page 599]
Solution 12.19	The level-two and -three gaskets are shown in Figure 12.35. topfloat Figure 12.35. Levels two and three of the Sierpinski gasket.
Solution 12.20	The printReverse() method is not tail recursive because in that method the recursive call is not the last statement executed.
Solution 12.21	The countChar() method is tail recursive. The recursive calls are not the last statements in the method definition. However, each of the recursive calls would be the last statement executed by the method.