Java Reference
In-Depth Information
Section 18.2 Recursion Concepts
• When a recursive method is called (p. 778) to solve a problem, it can solve only the simplest
case(s), or base case(s). If called with a base case (p. 778), the method returns a result.
• If a recursive method is called with a more complex problem than a base case, it typically divides
the problem into two conceptual pieces—a piece that the method knows how to do and a piece
that it does not know how to do.
• To make recursion feasible, the piece that the method does not know how to do must resemble
the original problem, but be a slightly simpler or smaller version of it. Because this new problem
resembles the original problem, the method calls a fresh copy of itself to work on the smaller
problem—this is called the recursion step (p. 778).
• For recursion to eventually terminate, each time a method calls itself with a simpler version of
the original problem, the sequence of smaller and smaller problems must converge on a base case.
When, the method recognizes the base case, it returns a result to the previous copy of the method.
• A recursive call may be a call to another method, which in turn makes a call back to the original
method. Such a process still results in a recursive call to the original method. This is known as
an indirect recursive call or indirect recursion (p. 778).
Section 18.3 Example Using Recursion: Factorials
• Either omitting the base case or writing the recursion step incorrectly so that it does not converge
on the base case can cause infinite recursion (p. 781), eventually exhausting memory. This error
is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution.
Section 18.5 Example Using Recursion: Fibonacci Series
• The Fibonacci series (p. 783) begins with 0 and 1 and has the property that each subsequent Fi-
bonacci number is the sum of the preceding two.
• The ratio of successive Fibonacci numbers converges on a constant value of 1.618…, a number
that has been called the golden ratio or the golden mean (p. 783).
• Some recursive solutions, such as Fibonacci, result in an “explosion” of method calls.
Section 18.6 Recursion and the Method-Call Stack
• The executing method is always the one whose stack frame is at the top of the stack, and the stack
frame for that method contains the values of its local variables.
Section 18.7 Recursion vs. Iteration
• Both iteration and recursion are based on a control statement: Iteration uses a repetition state-
ment, recursion a selection statement.
• Both iteration and recursion involve repetition: Iteration explicitly uses a repetition statement,
whereas recursion achieves repetition through repeated method calls.
• Iteration and recursion each involve a termination test: Iteration terminates when the loop-con-
tinuation condition fails, recursion when a base case is recognized.
• Iteration with counter-controlled repetition and recursion each gradually approach termination:
Iteration keeps modifying a counter until the counter assumes a value that makes the loop-con-
tinuation condition fail, whereas recursion keeps producing simpler versions of the original prob-
lem until the base case is reached.
• Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the
loop-continuation test never becomes false, whereas infinite recursion occurs if the recursion step
does not reduce the problem each time in a manner that converges on the base case.
