of Recursion in Visual C#.NET

Painting EAN13 in Visual C#.NET of Recursion

Suppose you have a data type that represents a maze. A maze is basically a grid, and at each point on the grid you might be able to turn left, turn right, move up, or move down. You ll often be able to move in more than one direction.

How do you write a program to find its way through the maze If you use recursion, the answer is fairly straightforward. You start at the beginning and then try all possible paths until you find your way out of the maze. The first time you visit a point, you try to move left. If you can t move left, you try to go up or down, and if you can t go up or down, you try to go right. You don t have to worry about getting lost because you drop a few bread crumbs on each spot as you visit it, and you don t visit the same spot twice.

Figure 17-1 Recursion can be a valuable tool in the battle against complexity when used to attack suitable problems.

Here s how the recursive code looks:

bool FindPathThroughMaze( Maze maze, Point position ) { // if the position has already been tried, don't try it again if ( AlreadyTried( maze, position ) ) { return false; } // if this position is the exit, declare success if ( ThisIsTheExit( maze, position ) ) { return true; } // remember that this position has been tried RememberPosition( maze, position ); // check the paths to the left, up, down, and to the right; if // any path is successful, stop looking if ( MoveLeft( maze, position, &newPosition ) ) {

if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } if ( MoveUp( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } if ( MoveDown( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } if ( MoveRight( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } return false; }

The first line of code checks to see whether the position has already been tried. One key aim in writing a recursive routine is the prevention of infinite recursion. In this case, if you don t check for having tried a point, you might keep trying it infinitely. The second statement checks to see whether the position is the exit from the maze. If ThisIsTheExit() returns true, the routine itself returns true. The third statement remembers that the position has been visited. This prevents the infinite recursion that would result from a circular path. The remaining lines in the routine try to find a path to the left, up, down, and to the right. The code stops the recursion if the routine ever returns true, that is, when the routine finds a path through the maze. The logic used in this routine is fairly straightforward. Most people experience some initial discomfort using recursion because it s self-referential. In this case, however, an alternative solution would be much more complicated and recursion works well.

Here are some tips for using recursion:

Make sure the recursion stops Check the routine to make sure that it includes a nonrecursive path. That usually means that the routine has a test that stops further recursion when it s not needed. In the maze example, the tests for AlreadyTried() and ThisIsTheExit() ensure that the recursion stops. Use safety counters to prevent infinite recursion If you re using recursion in a situation that doesn t allow a simple test such as the one just described, use a safety counter to prevent infinite recursion. The safety counter has to be a variable that s not re-created each time you call the routine. Use a class member variable or pass the safety counter as a parameter. Here s an example: