Recursive Algorithms Demystified: Solving Mazes with Depth-First Search in Java
Posted inRecursion

Recursive Algorithms Demystified: Solving Mazes with Depth-First Search in Java

Recursive Algorithms Demystified: Solving Mazes with Depth-First Search in Java

 

Introduction

Recursion is one of those core programming concepts that often intimidates developers when they first encounter it. Yet, when understood deeply, it becomes one of the most elegant tools in your arsenal. In this post, we’ll demystify recursive algorithms through a concrete and visual example: solving a maze using Depth-First Search (DFS) in Java. We’ll walk from the simple concept of recursion to implementing a recursive DFS algorithm that finds a path through a small maze grid.

1. Understanding Recursion and Depth-First Search

Recursion occurs when a function calls itself to solve a smaller instance of the same problem. In pathfinding terms, DFS explores each path fully before backtracking and trying another, making recursion a natural fit. The key is to have a clear base case (when to stop) and a recursive case (when to continue).

Let’s start by understanding the DFS approach:

  • Pick a starting cell.
  • Visit it and mark it as visited.
  • Recursively visit its unvisited neighbors.
  • If the destination is found, unwind the recursion, preserving the path.

This can be visualized as a depth-first exploration of the maze tree.

2. Representing the Maze in Java

We can represent our maze as a 2D grid of integers, where 0 represents an empty path and 1 represents a wall. We’ll define the start and end points explicitly.

public class MazeSolver {\n    private static final int PATH = 0;\n    private static final int WALL = 1;\n    private static final int VISITED = 2;\n\n    private int[][] maze = {\n        {0, 1, 0, 0, 0},\n        {0, 1, 0, 1, 0},\n        {0, 0, 0, 1, 0},\n        {1, 1, 0, 0, 0},\n        {0, 0, 0, 1, 0}\n    };\n\n    private int rows = maze.length;\n    private int cols = maze[0].length;\n}

This 5×5 grid defines a simple maze where some cells are blocked. Our goal is to move from (0, 0) (top-left) to (4, 4) (bottom-right).

3. Implementing Recursive DFS

DFS explores each possible path recursively. Here, we can create a helper function solveMaze() that receives the current position and checks for valid moves.

public boolean solveMaze(int row, int col) {\n    // Base case: destination reached\n    if (row == rows - 1 && col == cols - 1) {\n        maze[row][col] = VISITED;\n        return true;\n    }\n\n    // Check bounds and obstacles\n    if (row < 0 || col < 0 || row >= rows || col >= cols || maze[row][col] != PATH) {\n        return false;\n    }\n\n    // Mark current cell as visited\n    maze[row][col] = VISITED;\n\n    // Explore neighbors: right, down, left, up\n    if (solveMaze(row, col + 1) || // right\n        solveMaze(row + 1, col) || // down\n        solveMaze(row, col - 1) || // left\n        solveMaze(row - 1, col)) { // up\n        return true;\n    }\n\n    // Backtracking: unmark cell\n    maze[row][col] = PATH;\n    return false;\n}

This recursive logic ensures that we explore deeply along one path before backtracking. The base case checks whether we’ve reached the goal, while invalid moves or walls return false.

4. Visualizing the Search and Results

To make our maze traversal easier to follow, let’s print the maze after every move. This helps debug and understand the recursive depth visually.

private void printMaze() {\n    for (int[] row : maze) {\n        for (int cell : row) {\n            System.out.print(cell + " ");\n        }\n        System.out.println();\n    }\n    System.out.println();\n}

Now, run the algorithm:

public static void main(String[] args) {\n    MazeSolver solver = new MazeSolver();\n    if (solver.solveMaze(0, 0)) {\n        System.out.println("Path found!");\n    } else {\n        System.out.println("No path found.");\n    }\n    solver.printMaze();\n}

You’ll see how the recursive calls explore paths, mark visited cells, and finally trace a route to the destination.

5. Performance and Optimization Considerations

DFS is a great algorithm for finding a path but not necessarily the shortest one. Because it follows one branch deeply before exploring others, performance can degrade in large mazes with many dead ends. However, for small to medium grids, recursive DFS is simple, clear, and effective.

  • Stack Depth: Each recursive call adds a frame to the call stack. For very large mazes, consider using an iterative version with an explicit stack to prevent stack overflow.
  • Visited Marking: Always mark cells correctly to prevent infinite loops in cyclic paths.
  • Path Tracking: To record the path explicitly, maintain a List<int[]> representing the current route and copy it when a full path is found.

Conclusion

Through this Java DFS maze solver, we’ve seen how recursion naturally expresses exploration problems. With proper base cases, backtracking, and marking logic, recursive DFS becomes intuitive and powerful. While not always the fastest, it’s a perfect gateway to understanding recursion and search algorithms conceptually.

Try extending this algorithm by adding diagonal moves or visualizing the recursion stack in real-time!

 

Useful links: