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)?
12.1.1.3. mystery2(5)?
12.2 Recursive Definition
12.2.2 Drawing a Nested Pattern
Self-Study Exercises
12.2.2.1. Recursive definition: 2^n.
12.2.2.2. Recursive definition: x^n.
12.2.2.3. Equivalent definitions?
12.3 Recursive String Methods
12.3.1 Printing a String
Self-Study Exercise
12.3.1.2. What’s the output?
12.3.2 Printing the String Backward
Self-Study Exercises
12.3.2.1. Count down.
12.3.2.2. Count down by two.
12.3.3 Counting Characters in a String
Self-Study Exercises
12.3.3.1. Sum of 1 to N.
12.3.4 Translating a String
Self-Study Exercise
12.3.4.1. Add Blanks.
12.3.5 Printing all Possible Outcomes when Tossing N Coins
Self-Study Exercise
12.3.5.1. Chess Outcomes.
12.4 Recursive Array Processing
12.4.2 Information Hiding
Self-Study Exercise
12.4.2.1. Recursive search.
12.4.3 Recursive Selection Sort
Self-Study Exercises
12.4.3.1. Find Max.
12.4.3.2. Selection sort.
12.5 Example: Drawing (Recursive) Fractals
12.5.1 Nested Squares
Self-Study Exercises
12.5.1.1. Nested Boxes.
12.6 OBJECT-ORIENTED DESIGN: Tail Recursion
Self-Study Exercises
12.6.1. printReverse() tail recursive?
12.6.2. countChar() tail recursive?
12.9 From the Java Library: javax.swing.JComboBox
12.9.1 A JComboBoxExample
Self-study Exercises
12.9.1.1. Recursive Patterns.
You have attempted of activities on this page.
