Java Reference
In-Depth Information
The problem-solving techniques we have employed so far fall under the heading of
classical
iteration,
also known as the
iterative approach.
Iteration (Iterative)
A programming technique in which you describe actions to be repeated
using a loop.
In this chapter we will explore a new technique known as
recursion.
Recursion (Recursive)
A programming technique in which you describe actions to be repeated
using a method that calls itself.
You have spent so much time writing solutions iteratively that it will take a while
to get used to thinking about problems recursively. This chapter will help you get
acclimated.
If you're standing in line, you might wonder what position you're in. Are you number
10 in the line? Number 20? How would you find out?
Most people would solve this problem iteratively, by counting the people in the
line: one, two, three, and so on. This approach is like a
while
loop that continues
while there are more people left to count. The iterative approach is a natural one, but
it has some limitations. For example, what if the person in front of you is taller than
you? Will you be able to see past that person to count all the people in front of him?
And what if the line goes around the block and you can't see around the corner to
count the people there?
Can you think of another way to determine your position in the line? To think
about the problem recursively, you have to imagine that all the people standing in line
work together to solve the problem: Instead of having one person do all of the count-
ing, each person is responsible for a little piece.
One cooperative approach would be to ask the person in front of you what your
place in line is. That person might ask another person, who might ask another person.
But that doesn't help much, because it just leads to a bunch of people saying, “This
guy wants to know what place he is in line. Does anyone know?” Someone would
probably eventually start counting and solve the problem iteratively.
Search WWH ::
Custom Search