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 kristen is standing at the origin facing east, and suppose that there is a beeper somewhere along 1st Street. We want kristen to go to the beeper and pick it up and return to the origin.
kristen.retrieveBeeper()
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.
from karel.robota import Robot
from karel.robota import East
from karel.robota import world
from karel.robota import window
class BeeperFinder(Robot):
def retrieveBeeper(self):
self.findBeeper()
self.pickBeeper()
self.turnLeft();
self.turnLeft()
self.returnToWestWall()
def findBeeper(self):
pass
def returnToWestWall(self):
pass
Well, that will certainly do the job, if we can write the other two new instructions. Let's now attack findBeeper. We know that there is a beeper somewhere on 1st Street. We also know that kristen is on 1st Street facing East. It may be that kristen is already on the beeper corner, in which case there is nothing to do. Therefore we may get started by writing:
def findBeeper(self):
if not self.nextToABeeper():
...
This will correctly terminate having done nothing if kristen is already at the beeper corner. Suppose next that the beeper is on some other corner. Then kristen needs to move, of course, and check other corners.
def findBeeper(self):
if not self.nextToABeeper():
self.move()
???
Well, what does kristen need to do after a move? Notice that kristen 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 kristen's current location or farther East of it. But this is exactly the same situation (relatively) that kristen was in when it started this task. Therefore, we can conclude that what kristen needs to do now is exactly findBeeper and nothing more.
def findBeeper(self):
if not self.nextToABeeper():
self.move()
self.findBeeper()
Notice that findBeeper has been completely defined, but it has been defined by using findBeeper 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 findBeeper as either "nothing", if kristen is already on the beep corner, or "move; findBeeper", if kristen is anywhere else. It is also necessary to know before we start executing such an instruction that there is, indeed, a beeper somewhere in kristen's path. Otherwise, after every move, the reexecution of findBeeper will find that the test is true, generating yet another reexecution of findBeeper without end.
The other instruction, returnToWestWall 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.
def returnToWestWall(self):
if self.frontIsClear():
self.move()
self.returnToWestWall()
Programming with recursion is a very powerful and sometimes error-prone activity. It will be taken up again in Chapter 7. Notice that its purpose is to get a robot to repeat an action (move, in this case) a possibly unknown number of times.