Recursion - Building Java Programs: A Back to Basics Approach - page 761

Chapter Summary

Recursion is an algorithmic technique in which a method
calls itself. A method that uses recursion is called a recur-
sive method.

A recursive method without a base case, or one in which
the recursive case doesn't properly transition into the base
case, can lead to infinite recursion.

Recursive methods include two cases: a base case that the
method can solve directly without recursion, and a recur-
sive case in which the method reduces a problem into a
simpler problem of the same kind using a recursive call.

A helper method is written to help solve a subtask of an
overall problem. Recursive helper methods often have
parameters in addition to the ones passed to the overall
recursive method that calls them, to allow them to more
easily implement the overall recursive solution.

Recursive method calls work internally by storing infor-
mation about each call into a structure called a call stack.
When the method calls itself, information about the call is
placed on top of the stack. When a method call finishes
executing, its information is removed from the stack and
the program returns to the call underneath.

Recursion can be used to draw graphical figures in com-
plex patterns, including fractal images. Fractals are images
that are recursively self-similar, and they are often referred
to as “infinitely complex.”

Self-Check Problems

Section 12.1: Thinking Recursively
1. What is recursion? How does a recursive method differ from a standard iterative method?

2. What are base cases and recursive cases? Why does a recursive method need to have both?

3. Consider the following method:

public static void mystery1(int n) {
if (n <= 1) {
System.out.print(n);
} else {
mystery1(n / 2);
System.out.print(", " + n);

}

}

For each of the following calls, indicate the output that is produced by the method:
a. mystery1(1);
b. mystery1(2);
c. mystery1(3);