Given the problem--a robot must clean all beepers from its current corner--we could easily write a loop that looks like the following.
public class Sweeper extends Robot
{
public void sweepCorner()
{ while ( nextToABeeper() )
{ pickBeeper();
}
}
...
}
This correctly solves the problem and is known as an iterative solution
("iterative" means that a loop of some sort, WHILE or
FOR- LOOP, was used). Contrast this solution with a recursive one.
public void sweepCorner()
{ if ( nextToABeeper() )
{ pickBeeper();
sweepCorner();
}
}
The difference between these two methods is very subtle. The first method, which uses the WHILE loop, is called once and the robot's focus never leaves the loop until it is finished, executing zero or more pickBeepers (depending on the initial number on the corner). What happens in the second, recursive, sweepCorner? Let's look at it very carefully.
If the robot is initially on an empty corner when the message is sent, nothing happens (similar to the WHILE loop). If it is on a corner with one beeper when the message is sent, the IF test is true, so the robot executes one pickBeeper instruction (thus emptying the corner). It then makes a second call of sweepCorner, remembering where it was in the first call. When sweepCorner is called the second time, the IF test is false, so nothing happens and the robot returns to the first call.
[initial instantiation of]
public void sweepCorner()
{ if ( nextToABeeper() )
{ pickBeeper();
sweepCorner(); // <-- This is the second call to
} //sweepCorner. The robot will return to
} //this point when that call
// finishes executing.
[second instantiation of]
public void sweepCorner()
{ if ( nextToABeeper() ) // <-- this is now false
{ pickBeeper();
sweepCorner();
}
}
Each call results in a separate instance (or instantiation) of the instruction sweepCorner. The robot must completely execute each instance, always remembering where it was in the previous instance so it can return there when it finishes.
The process for writing recursive robot instructions is very similar to that for writing loops:
Step 1: Consider the stopping condition (also called the base case)--what is the simplest case of the problem that can be solved? In the sweepCorner problem, the simplest, or base, case is when the robot is already on an empty corner.
Step 2: What does the robot have to do in the base case? In this example there's nothing to do.
Step 3: Find a way to solve a small piece of the larger problem if not in the base case. This is called "reducing the problem in the general case." In the sweepCorner problem, the general case is when the robot is on a corner with one or more beepers and the reduction is to pick up a beeper.
Step 4: Make sure the reduction leads to the base case. Again, in the above example of sweepCorner, by picking up one beeper at a time, the robot must eventually clear the corner of beepers, regardless of the original number present.
Let's compare and contrast iteration and recursion:
* An iterative loop must complete each iteration before beginning the next one.
* A recursive method typically begins a new instance before completing the current one. When that happens, the current instance is temporarily suspended, pending the completion of the new instance. Of course, this new instance might not complete before generating another one. Each successive instance must be completed in turn, last to first.
* Since EACH recursive instance is supposed to make some (often minimal) progress toward the base case, we should not use loops to control recursive calls. Thus, we will usually see an IF or an IF/ELSE in the body of a recursive new method, but not a WHILE.
Suppose we wanted to use recursion to move a robot named Karel to a beeper. How would we do it? Following the steps presented earlier:
* What is the base case? Karel is on the beeper.
* What does the robot have to do in the base case? Nothing.
* What is the general case? The robot is not on the beeper.
* What is the reduction? Move toward the beeper and make the recursive call.
* Does the reduction lead to termination? Yes, assuming the beeper is directly in front of the robot , the distance will get shorter by one block for each recursive call.
The final implementation follows.
public void findBeeper()
{ if ( ! nextToABeeper() )
{ move();
findBeeper();
}
}
Note that this problem could also have been easily solved with a WHILE loop. Let's look at a problem that is not easily solved with a WHILE loop. Remember the Lost Beeper Mine, the corner with a large number of beepers? Imagine we must write the following method in our search for the mine. A robot named Karel must walk east from its current location until it finds a beeper. The Lost Beeper Mine is due north of that intersection a distance equal to the number of moves Karel made to get from its current position to the beeper. Write the new method, findMine.
It is not easy to see how to solve this problem with a WHILE loop as we do not have any convenient way of remembering how many intersections have been traversed. Oh, we could probably come up with a very convoluted beeper-tracking scheme, but let's look at a recursive solution that's pretty straightforward. Again, we'll answer our questions:
* What is the base case? Karel is on the beeper.
* What does Karel have to do in the base case? turnLeft (this will face Karel north).
* What is the general case? Karel is not on the beeper.
* What is the reduction? Move one block forward, make the recursive call and have Karel execute a second move after the recursive call. This second move will be executed in all instances but the base case, causing Karel to make as many moves north after the base case as it did in getting to the base case.
* Does the reduction lead to termination? Yes, assuming the beeper is directly in front of Karel.
Let's look at the complete method:
public void findMine()
{ if ( nextToABeeper() )
{ turnLeft();
}
else
{ move();
findMine();
move();
}
}
How many turnLefts are executed? How many moves? How many calls to findMine?
A good way to think about recursion and the recursive call is in terms of the specification of the method itself. In the above case, the specification is that when a robot executes this instruction it will walk a certain number of steps, say k, to a beeper, turn left, and then walk k steps farther. Suppose we start the robot N steps away from the beeper (k = N). When we examine the method above, the ELSE clause has a move message first. That means that the robot is now N-1 steps from the beeper. Therefore, by the specification, the recursive (k = N-1) call will walk N-1 steps forward, turn left, and then walk N-1 steps beyond. We therefore need to supply one additional move message after the recursion to complete the required N steps.
It will take solving a number of problems and a good deal of staring before recursion becomes as comfortable to use as iteration. A large part of this is because recursion requires some intuition to see the correct reduction, especially in difficult problems. This intuition will come with practice, which is just what the sample problems are designed to provide.