Simple recursive algorithm mechanism

Question

Once this is instantiated and method traverse(0,0) is invoked, it will automatically solve the maze showing 7 as the path and 3 as "tried paths". I'm trying to understand this code but I get stuck at the first else statement in the traverse method.

public class Maze
{
    private final int TRIED = 3;
    private final int PATH = 7;
    private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
                             {1,0,1,1,1,0,1,1,1,1,0,0,1},
                             {0,0,0,0,1,0,1,0,1,0,1,0,0},
                             {1,1,1,0,1,1,1,0,1,0,1,1,1},
                             {1,0,1,0,0,0,0,1,1,1,0,0,1},
                             {1,0,1,1,1,1,1,1,0,1,1,1,1},
                             {1,0,0,0,0,0,0,0,0,0,0,0,0},
                             {1,1,1,1,1,1,1,1,1,1,1,1,1} };

public boolean traverse (int row, int column)
{
    boolean done = false;
    if (valid (row, column))
    {
       grid[row][column] = TRIED;
       // this cell has been tried
       if (row == grid.length-1 && column == grid[0].length-1)
          done = true;
          // the maze is solved
       else
       {
          done = traverse (row+1, column); 
          // down
          if (!done)
          done = traverse (row, column+1); 
          // right
          if (!done)
          done = traverse (row-1, column);
          // up

          if (!done)
          done = traverse (row, column-1);
          // left
       }
    if (done)
    // this location is part of the final path
    grid[row][column] = PATH;
    }
    return done;
}

//-----------------------------------------------------------------
//  Determines if a specific location is valid.
//-----------------------------------------------------------------
private boolean valid (int row, int column)
{
    boolean result = false;
    // check if cell is in the bounds of the matrix
    if (row >= 0 && row < grid.length && column >= 0 &&
       column < grid[row].length)
       // check if cell is not blocked and not previously tried
       if (grid[row][column] == 1)
       result = true;
       return result;
}

To my knowledge,

done = traverse (row+1, column);

This line is a recursive call and will move it down once, and will run the method again but what if it's not valid? Doesn't the whole method stop? I don't understand where the flow of control shifts after a certain spot is not valid.

For example, if [1][0] is not valid, does the control shift back to the [0][0] call and process the "going right" statement? Where and what does it mean by if (!done), i mean done only equals true when the maze is completely solved and if it is valid, done will equal true, so wouldn't the whole thing just stop?

tckmn · Accepted Answer · 2012-12-08 03:41:45Z

2

Here's your method:

public boolean traverse (int row, int column)
{
    boolean done = false;
    if (valid (row, column))
    {
       ...
    }
    return done;
}

Therefore, if the point is not valid, it will skip all of the testing and just return false.

answered Dec 8, 2012 at 3:41

tckmn

59.6k27 gold badges118 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Aaron Over a year ago

What happens after it returns false??

tckmn Over a year ago

@Aaron done gets set to false and it tries going in a different direction.

Patricia Shanahan · Accepted Answer · 2012-12-08 03:41:55Z

0

If the valid test fails, the next thing to execute is the "return done;" at the end of the method, which will return false. That will pass the information about the failure back to the caller.

answered Dec 8, 2012 at 3:41

Patricia Shanahan

26.2k4 gold badges42 silver badges75 bronze badges

Comments

Debobroto Das · Accepted Answer · 2012-12-08 03:43:53Z

0

at the first else the row and columns are checked for validity. If the row and columns are not valid the method will not stop instantly, because based on the value of done field the nested if blocks inside the first else will be executed.

answered Dec 8, 2012 at 3:43

Debobroto Das

8626 silver badges16 bronze badges

Collectives™ on Stack Overflow

Simple recursive algorithm mechanism

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related