Mastering Recursive Functions: Solve Mazes with Backtracking in Python

Recursion is one of the most powerful and expressive tools in a developer’s toolkit—but it’s also one of the most misunderstood. In this post, we’ll take a deep look at recursion through a practical lens: solving mazes using the backtracking algorithm. By the end, you’ll understand recursion not just in theory, but through hands-on, step-by-step Python code that brings it to life.

1. Understanding the Recursive Mindset

Before jumping into code, let’s establish what recursion really means: a function that calls itself to solve smaller instances of a problem. In our maze-solving scenario, this translates to the function trying to move in every valid direction until it finds the solution or realizes there isn’t one.

In maze terms, the backtracking approach means:

Start at a defined entry point
Move in each direction (up, down, left, right)
If a move leads closer to the exit, continue; otherwise, backtrack

Consider this idea like traversing a tree: explore one path, and if it fails, return to the last known state and try a different route.

2. Representing the Maze Using a Grid

We begin with a simple 2D list to represent the maze. We’ll use 0 for open paths and 1 for walls. Here’s a sample maze:

maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0]
]

The goal is to move from the top-left corner (0, 0) to the bottom-right corner (4, 4). We’ll build our solution to track the path along the way using a visited matrix and directions.

3. Building the Maze Solver with Recursion and Backtracking

Let’s define our recursive function solve_maze that uses backtracking. It will:

Check if the current position is valid and not visited
Mark the position as part of the path
Recurse in all four directions
Backtrack (unmark the path) if all directions fail

Here’s the core implementation:

def is_valid(maze, visited, row, col):
    rows = len(maze)
    cols = len(maze[0])
    return 0 <= row < rows and 0 <= col < cols and maze[row][col] == 0 and not visited[row][col]

def solve_maze(maze, visited, path, row, col):
    rows = len(maze)
    cols = len(maze[0])

    # Base case: reached goal
    if row == rows - 1 and col == cols - 1:
        path.append((row, col))
        return True

    if is_valid(maze, visited, row, col):
        visited[row][col] = True
        path.append((row, col))

        # Try all directions: down, right, up, left
        if (solve_maze(maze, visited, path, row + 1, col) or 
            solve_maze(maze, visited, path, row, col + 1) or 
            solve_maze(maze, visited, path, row - 1, col) or 
            solve_maze(maze, visited, path, row, col - 1)):
            return True

        # Backtrack
        path.pop()
        visited[row][col] = False

    return False

To run the function:

rows, cols = len(maze), len(maze[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
path = []

if solve_maze(maze, visited, path, 0, 0):
    print("Path to goal:", path)
else:
    print("No path found.")

4. Visualizing and Debugging the Recursion

To truly understand recursion and backtracking, visualization is key. Let’s enhance our code to print the path during search:

def print_maze_path(maze, path):
    display = [row[:] for row in maze]  # Deep copy
    for r, c in path:
        display[r][c] = '*'
    for row in display:
        print(' '.join(str(cell) for cell in row))

# After finding the path:
print_maze_path(maze, path)

This will print the maze with the valid path (marked with '*'), making it easier to grasp how the algorithm explores and backtracks.

5. Optimizations and Tips for Scalable Mazes

While our implementation is correct, here are ways to improve performance:

Prune early: Stop exploring paths that go too far from start or goal.
Memoization: In rare cyclic maze settings, caching explored positions can prevent rework.
Stack depth warnings: Python has a recursion limit (~1000 by default). For huge mazes, consider iterative DFS with your own stack.

To avoid hitting the recursion limit in large mazes, you can extend the limit with:

import sys
sys.setrecursionlimit(2000)

But this has limitations; going for an iterative form or breadth-first search may perform better at scale.

Conclusion

Solving mazes via recursive backtracking is a visually satisfying and educational way to level up your understanding of recursion. It teaches you about the call stack, path finding, and problem decomposition in a very intuitive way. Once you master this recursive pattern, you’ll be ready to apply it to puzzles, search algorithms, and even AI pathfinding techniques.

Happy coding—and may your paths all lead to exits!

Useful links: