This algorithm successfully gives me a path through a maze. The maze is a 2D binary matrix, and the target location is ‘9’.

The algorithm works by going through the ‘0’ path that reaches ‘9’ (base case) and recursively adds the previous locations to my path array.

I observed that removing the border detecting line at the top gives an index out of bounds error. but I am pretty sure this algo is breaking when the path reaches a wall.

It also works smoothly on matrices 200×200 or less and about 50% of the time at 250×250.

(As seen in the 100 width one below.)

```
public static boolean searchPath(int[][]maze, int x, int y, ArrayList<Integer> path){
if(x<0 || x>=maze[1].length || y<0 || y>=maze.length) return false;
if(maze[y][x] == 9){
path.add(x);
path.add(y);
return true;
}
if(maze[y][x] == 0){
maze[y][x] = 2;
int dx = -1;
int dy = 0;
if(searchPath(maze, x+dx, y+dy, path)){
path.add(x);
path.add(y);
return true;
}
dx = 1;
dy = 0;
if(searchPath(maze, x+dx, y+dy, path)){
path.add(x);
path.add(y);
return true;
}
dx = 0;
dy = -1;
if(searchPath(maze, x+dx, y+dy, path)){
path.add(x);
path.add(y);
return true;
}
dx = 0;
dy = 1;
if(searchPath(maze, x+dx, y+dy, path)){
path.add(x);
path.add(y);
return true;
}
}
return false;
}
```

### >Solution :

Stack space is limited, so you should only write a recursive algorithm when you know that it will use a reasonable amount of it.

Using recursive DFS to find your way out of an NxM maze can use O(N*M) stack space — not reasonable.

You could write DFS using a separate stack data structure, but really you should use BFS with a queue. It’s a little simpler, and you will get the shortest path.