# The Recursive Maze Problem

Earlier this year, when I was looking for work, I got the same recursive maze problem three interviews in a row. Recursion is cute and clever, but you generally want to use iterative solutions in production.

Usually, you get a string representation of the maze, something like:

```ms = '''
S####
....#
#.###
....G
##..#
...##
#..##
'''
```

So then you need to parse that into a list of lists, which isn’t difficult:

```def maze_string_to_list_of_lists(maze: str) -> []:
rows = maze.split()
new_maze = []
for row in rows:
new_row = [i for i in row]
new_maze.append(new_row)
return new_maze
```

Next, I like to write a function to return cells orthogonal to some cell location. This originally considered cells north, south, east, and west of a location, but then I limited it to just south and east, because this is recursive and we have to worry about the stack size in Python. (Because recursion is as stupid as it is clever.)

```def orthogonals(row: int, col: int, row_limit: int, col_limit: int) -> []:
result = []
# check input
if row < 0 or row >= row_limit:
return result
if col < 0 or col >= col_limit:
return result
# compute output
s = [row+1, col]
e = [row, col+1]
# check computed output
if s < row_limit:
result.append(s)
if e < col_limit:
result.append(e)
return result
```

Finally, the meat and potatoes. Yeah, so `SOLN` is a global variable that’s laying around, which is bad. You know what else is bad? Recursive maze solvers.

```SOLN = []

def find_path(row: int, col: int, maze: list) -> bool:
if maze[row][col] == 'G':
SOLN.append([row, col])
return True
if maze[row][col] == '#':
return False
SOLN.append([row, col])
orthos = orthogonals(row, col, len(maze), len(maze))
for ortho in orthos:
if ortho in SOLN:
pass
if find_path(ortho, ortho, maze):
return True
SOLN.pop()
return False
```

References:

• (Recursion: Solving a Maze)[https://www.cs.bu.edu/teaching/alg/maze/]
• (Backtracking: Rat in a Maze)[http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/]

This site uses Akismet to reduce spam. Learn how your comment data is processed.