Recursion - Data Structures and Abstractions with Java - page 154

R epetition is a major feature of many algorithms. In fact, repeating actions rapidly is a key ability
of computers. Two problem-solving processes involve repetition; they are called iteration and
recursion. In fact, most programming languages provide two kinds of repetitive constructs, iterative
and recursive.
You know about iteration because you know how to write a loop. Regardless of the loop con-
struct you use— for , while , or do —your loop contains the statements that you want to repeat and a
mechanism for controlling the number of repetitions. You might have a counted loop that counts
repetitions as 1, 2, 3, 4, 5, or 5, 4, 3, 2, 1. Or the loop might execute repeatedly while a boolean
variable or expression is true. Iteration often provides a straightforward and efficient way to imple-
ment a repetitive process.
At times, iterative solutions are elusive or hopelessly complex. For some problems, discovering
or verifying such solutions is not a simple task. In these cases, recursion can provide an elegant alter-
native. Some recursive solutions can be the best choice, some provide insight for finding a better
iterative solution, and some should not be used at all because they are grossly inefficient. Recursion,
however, remains an important problem-solving strategy.
This chapter will show you how to think recursively.

What Is Recursion?

7.1

You can build a house by hiring a contractor. The contractor in turn hires several subcontractors to
complete portions of the house. Each subcontractor might hire other subcontractors to help. You
use the same approach when you solve a problem by breaking it into smaller problems. In one spe-
cial variation of this problem-solving process, the smaller problems are identical except for their
size. This special process is called recursion .

Suppose that you can solve a problem by solving an identical but smaller problem. How will
you solve the smaller problem? If you use recursion again, you will need to solve an even smaller
problem that is just like the original problem in every other respect. How will replacing a problem
with another one ever lead to a solution? One key to the success of recursion is that eventually you
will reach a smaller problem whose solution you know because either it is obvious or it is given.
The solution to this smallest problem is probably not the solution to your original problem, but it
can help you reach it. Either just before or just after you solve a smaller problem, you usually con-
tribute a portion of the solution. This portion, together with the solutions to the other, smaller prob-
lems, provides the solution to the larger problem.
Let's look at an example.

VideoNote

Introducing recursion

7.2

Example: The countdown. It's New Year's Eve and the giant ball is falling in Times Square. The
crowd counts down the last 10 seconds: “10, 9, 8, . . .” Suppose that I ask you to count down to 1
beginning at some positive integer like 10. You could shout “10” and then ask a friend to count
down from 9. Counting down from 9 is a problem that is exactly like counting down from 10,
except that there is less to do. It is a smaller problem.
To count down from 9, your friend shouts “9” and asks a friend to count down from 8. This
sequence of events continues until eventually someone's friend is asked to count down from 1. That
friend simply shouts “1.” No other friend is needed. You can see these events in Figure 7-1.