# Thread: Recursion error

1. Member
Join Date
Mar 2012
Location
Vestal, NY
Posts
36
Rep Power
0

## Recursion error

I'm writing a simple recursion program that is supposed to find a path through a "maze".
Java Code:
```//CLASS MAZESEARCH (driver)
public class MazeSearch
{
public static void main(String[] args)
{
Maze labyrinth = new Maze();
System.out.println(labyrinth);
if(labyrinth.traverse(0, 0))
{
System.out.println("The maze was successfully solved!");
}
else
{
System.out.println("There is no possible path.");
}
System.out.println(labyrinth);
}
}
//CLASS MAZE
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;
if(row == grid.length - 1 && column == grid[0].length - 1)
{
done = true;
}
else
{
done = traverse(row + 1, column + 1);
if(!done)
{
done = traverse(row, column + 1);
}
if(!done)
{
done = traverse(row - 1, column);
}
if(!done)
{
done = traverse(row, column - 1);
}
}
if(done)
{
grid[row][column] = PATH;
}
}
return done;
}
private boolean valid(int row, int column)
{
boolean result = false;
if(row >= 0 && row < grid.length && column >= 0 && column < grid[row].length)
{
if(grid[row][column] == 1)
{
result = true;
}
}
return result;
}
public String toString()
{
String result = "\n";
for(int row = 0; row < grid.length; row++)
{
for(int column = 0; column < grid[row].length; column++)
{
result += grid[row][column] + "";
}
result += "\n";
}
return result;
}
}```
Here is the output:
"1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111

There is no possible path.

3330330003333
1033303333003
0000303030300
1110333030333
1010000333003
1011111103333
1000000000000
1111111111111"

Theres the problem in red...why is it not seeing that 1 below the 3 on the left?

2. ## Re: Recursion error

why is it not seeing that 1 below the 3 on the left?
Add some printlns to the code to print out what it is doing so you can see where the execution goes and what the values of variables are as it executes

3. ## Re: Recursion error

I'm not really sure I understand your code but it just seems like this part:
Java Code:
```                done = traverse(row + 1, column + 1);
if(!done)                {
done = traverse(row, column + 1);
}
if(!done)                {
done = traverse(row - 1, column);
}
if(!done)                {
done = traverse(row, column - 1);
}```
is meant to search up,down,left and right from a given index in the 2d array...

if thats so, then the first statement is wrong and should look like this:
Java Code:
`                done = traverse(row + 1, column);`
so that you are checking 'down' and not 'down-right'

looking at your output again it seems like all of the 1's that were converted to 3's were accessible through the down-right path up until where it had stopped.
Last edited by ozzyman; 03-11-2012 at 02:57 AM.

4. Member
Join Date
Mar 2012
Location
Vestal, NY
Posts
36
Rep Power
0

## Re: Recursion error

that worked thanks ozzyman

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•