So far, in all of our examples, when we ask a robot to move from one point to another, we have known exactly how far it would move. There are many situations, however, in which this is not true. Suppose, for example, that a robot named Kristin is standing at the origin facing east, and suppose that there is a beeper somewhere along 1st Street. We want Kristin to go to the beeper and pick it up and return to the origin.
Kristin.retrieve_beeper();
If we knew that the beeper was on 1st and 23rd we would be able to write a program to do this. If we knew that it was no more than, say, 15 blocks away, then we could find a solution. (How?) But what if we don't know how far it is. To get started, let's build a new class: Beeper_Finder.
class Beeper_Finder extends Robot
{
void retrieve_beeper()
{ find_beeper();
pickBeeper();
turnLeft();
turnLeft();
return_to_west_wall();
}
void find_beeper(){...}
void return_to_west_wall(){...}
}
Well, that will certainly do the job, if we can write the other two new instructions. Let's now attack find_beeper. We know that there is a beeper somewhere on 1st Street. We also know that Kristin is on 1st Street facing East. It may be that Kristin is already on the beeper corner, in which case there is nothing to do. Therefore we may get started by writing:
void find_beeper()
{ if (! nextToABeeper())
{
...
}
}
This will correctly terminate having done nothing if Kristin is already at the beeper corner. Suppose next that the beeper is on some other corner. Then Kristin needs to move, of course, and check other corners.
void find_beeper()
{ if (! nextToABeeper())
{ move();
???
}
}
Well, what does Kristin need to do after a move? Notice that Kristin is on a different corner than the one on which it started and that the original corner was checked and found to lack a beeper. Therefore we may conclude that the beeper is now (after the move) either at Kristin's current location or farther East of it. But this is exactly the same situation (relatively) that Kristin was in when it started this task. Therefore, we can conclude that what Kristin needs to do now is exactly find_beeper and nothing more.
void find_beeper()
{ if (! nextToABeeper())
{ move();
find_beeper();
}
}
Notice that find_beeper has been completely defined, but it has been defined by using find_beeper itself. How can this be done? Well, suppose we needed to empty an ocean with a bucket. To perform emptyTheOcean, we first ask if the ocean is empty. If so, we are done. Otherwise we just remove one bucket of water from the ocean and then emptyTheOcean.
The important thing in such a definition, called a recursive definition, is that we don't define a thing in terms of precisely itself. We define a thing in terms of a simpler or smaller version of itself, and also define the smallest or simplest version separately. Here we define find_beeper as either "nothing", if Kristin is already on the beep corner, or "move; find_beeper", if Kristin is anywhere else. It is also necessary to know before we start executing such an instruction that there is, indeed, a beeper somewhere in Kristin's path. Otherwise, after every move, the reexecution of find_beeper will find that the test is true, generating yet another reexecution of find_beeper without end.
The other instruction, return_to_west_wall is similar, except for the test. Here, however we know that there is a wall to the west. If we can guarantee that the robot is also facing west, then the following instruction will serve.
void return_to_west_wall()
{ if (frontIsClear())
{ move();
return_to_west_wall();
}
}
Programming with recursion is a very powerful and sometimes error-prone activity. It will be taken up again in Chapter 6. Notice that its purpose is to get a robot to repeat an action (move, in this case) a possibly unknown number of times.