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.
Section 12.10 Chapter Summary
Subsection 12.10.1 Technical 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 |
Subsection 12.10.2 Important 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
JComboBoxcomponent is used to represent a GUI drop-down menu.
Solutions 12.10.3 Solutions to Self-Study Exercises
12.1 Introduction
12.1.1 Recursion as Repetition
Self-Study Exercises
12.1.1.1.
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.2 Recursive Definition
12.2.2 Drawing a Nested Pattern
Self-Study Exercises
12.2.2.1. Recursive definition: 2^n.
Solution.
\begin{equation*}
2^n = \begin{cases} 1 \amp \text{if } n = 0 \text{ // Base case}\\
2 * 2^{n-1} \amp \text{if n > 0 // Recursive case} \end{cases}
\end{equation*}
12.2.2.2. Recursive definition: x^n.
Solution.
\begin{equation*}
x^n = \begin{cases} 1 \amp \text{if } n = 0 \text{ // Base case}\\
x * x^{n-1} \amp \text{if n > 0 // Recursive case} \end{cases}
\end{equation*}
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.
12.3 Recursive String Methods
12.3.1 Printing a String
Self-Study Exercise
12.3.1.2. What’s the output?
Solution.
olleh
12.3.2 Printing 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.3 Counting 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.4 Translating a String
Self-Study Exercise
12.3.4.1. Add Blanks.
Solution.
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));
}
12.3.5 Printing 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.4 Recursive Array Processing
12.4.2 Information 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.3 Recursive 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.5 Example: Drawing (Recursive) Fractals
12.5.1 Nested 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.6 OBJECT-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.9 From the Java Library: javax.swing.JComboBox
12.9.1 A 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()
You have attempted of activities on this page.
