# Java, Java, Java: Object-Oriented Problem Solving, 2022E

## Section12.10Chapter Summary

### Subsection12.10.1Technical Terms

 base case recursion parameter computational overhead recursive case head-and-tail algorithm recursive definition iterative method recursive method last-in-first-out (LIFO) self-similarity method call stack tail recursive

### Subsection12.10.2Important Points

• A recursive definition is one that defines the nth case of a concept in terms of the $$(n-1)$$st case plus a limiting condition. It is based on the idea of breaking a problem up into smaller, self-similar problems.
• A recursive method is one that calls itself. It is usually defined in terms of a base case or limiting case, which stops the recursive process, and a recursive case, which breaks the method into a smaller, self-similar copy of itself. A recursion parameter is generally used to control the recursion.
• An iterative algorithm is one that uses some kind of loop as its control structure. Any algorithm that can be done iteratively can also be done recursively, and vice versa.
• Because method calling is relatively costly both in terms of memory used and CPU time involved, a recursive algorithm is generally less efficient than an iterative one that does the same thing.
• In designing recursive algorithms, the base case defines a limit. Each level of recursion should make progress toward the limit, and the algorithm should eventually reach the limit. The limit is usually expressed in terms of the recursion parameter.
• A recursive method is tail recursive if and only if each of its recursive calls is the last action executed by the method.
• A Swing JComboBox component is used to represent a GUI drop-down menu.

### Solutions12.10.3Solutions to Self-Study Exercises

#### 12.1Introduction12.1.1Recursion as Repetition

##### Self-Study Exercises
###### 12.1.1.1.mystery(5)?
Solution.
The output would be: 0 1 2 3 4 5 6. The 6 is printed before the recursion stops.
###### 12.1.1.2.mystery(100)?
Solution.
The output produced by mystery(100) would be 100.
###### 12.1.1.3.mystery2(5)?
Solution.
The output produced by mystery(5) would be: 5 4 3 2 1 0 -1 -2 ... In other words, this is an infinite recursion.

#### 12.2Recursive Definition12.2.2Drawing a Nested Pattern

##### Self-Study Exercises
###### 12.2.2.1.Recursive definition: 2^n.
Solution.
2^n =
1, if n = 0             // Base case
2 * 2^(n-1), if n > 0   // Recursive case

###### 12.2.2.2.Recursive definition: x^n.
Solution.
x^n =
1, if n = 0             // Base case
x * x^(n-1), if n > 0   // Recursive case

###### 12.2.2.3.Equivalent definitions?
Solution.
Yes, the two definitions for nested boxes are equivalent. Suppose the square starts out with a side of 20. Both will draw squares with sides of 20, 15, 10, 5. If side starts out at 5, both draw a square of size 5. For values less than 5, nothing would be drawn.

Solution.
olleh

#### 12.3.2Printing the String Backward

##### Self-Study Exercises
###### 12.3.2.1.Count down.
Solution.
/** 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()

###### 12.3.2.2.Count down by two.
Solution.
/** 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()


#### 12.3.3Counting Characters in a String

##### Self-Study Exercises
###### 12.3.3.1.Sum of 1 to N.
Solution.
int sum1toN(int N) {
if (N == 0)
return 0;
else
return N + sum1toN(N-1);
}


#### 12.3.4Translating a String

##### Self-Study Exercise
Solution.
String addBlanks(String s) {
if (s.length() == 0)
return "";
else if (s.charAt(0) == ' ')
return ' ' + s.charAt(0) + addBlanks(s.substring(1));
else
}


#### 12.3.5Printing all Possible Outcomes when Tossing N Coins

##### Self-Study Exercise
###### 12.3.5.1.Chess Outcomes.
Solution.
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()


#### 12.4Recursive Array Processing12.4.2Information Hiding

##### Self-Study Exercise
###### 12.4.2.1.Recursive search.
Solution.
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()


#### 12.4.3Recursive Selection Sort

##### Self-Study Exercises
###### 12.4.3.1.Find Max.
Solution.
/** 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()

###### 12.4.3.2.Selection sort.
Solution.
/** 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); // Call the recursive method
}


#### 12.5Example: Drawing (Recursive) Fractals12.5.1Nested Squares

##### Self-Study Exercises
###### 12.5.1.1.Nested Boxes.
Solution.
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
}
} // drawBoxesIterative()


#### 12.6OBJECT-ORIENTED DESIGN: Tail Recursion

##### Self-Study Exercises
###### 12.6.1.printReverse() tail recursive?
Solution.
The printReverse() method is not tail recursive because in that method the recursive call is not the last statement executed.
###### 12.6.2.countChar() tail recursive?
Solution.
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.

#### 12.9From the Java Library: javax.swing.JComboBox12.9.1A JComboBoxExample

##### Self-study Exercises
###### 12.9.1.1.Recursive Patterns.
Solution.
private void  drawBoxesRev(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;
drawBoxesRev(g, level - 1, newLocX, newLocY,
side - 2 * dside, delta);
}
} // drawBoxesRev()