5.10 Introduction to Repetition

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.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.

public class Beeper_Finder extends Robot 
{
	public void retrieveBeeper() 
	{	findBeeper();
		pickBeeper();
		turnLeft();
		turnLeft();
		returnToWestWall();
	}
	
	public void findBeeper(){...}

	public void returnToWestWall(){...}
}

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 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:

public void findBeeper() 
{	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.

public void findBeeper() 
{	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 findBeeper and nothing more.

public void findBeeper() 
{	if (! nextToABeeper()) 
	{	move();
		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 Kristin is already on the beep corner, or "move; findBeeper", 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 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.

public void returnToWestWall()
{	if (frontIsClear()) 
	{	move();
		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.