Skip to main content
Logo image

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

Ralph Morelli, Ralph Walde, Beryl Hoffman

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 JComboBox component 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. 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.2 Recursive Definition
12.2.2 Drawing 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.

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.
PrevTopNext