Recursive Backtracking is the most popular maze generation algorithm. It uses depth-first search (DFS) with random neighbor selection to carve passages through a grid. The result is a "perfect" maze — one where every cell is reachable and there is exactly one path between any two points.
Recursive backtracking creates mazes with long, winding corridors and relatively few dead ends. This produces a satisfying solving experience — you follow a path for a while before hitting a junction. Compare this to Prim's algorithm, which creates shorter, bushier passages.
This is the engine behind our Classic Maze game and countless indie games. It's popular because it's simple to implement, efficient (O(n) time), and creates visually appealing mazes. Roguelikes like Spelunky use variants of this algorithm for procedural dungeon generation.
| Time Complexity | O(n) — visits each cell exactly once |
| Space Complexity | O(n) — stack can grow to maze size in worst case |
| Perfect Maze? | ✅ Yes — one path between any two cells |
| Corridor Style | Long, winding passages with few branches |
| Dead-End Ratio | Low — fewer dead ends than Prim's or Kruskal's |
| Based On | Depth-First Search with random neighbor selection |
Every maze you play on HTML Maze is generated with recursive backtracking. Notice the long corridors and winding paths — that's the DFS signature.
A perfect maze has exactly one path between any two cells — no loops, no isolated areas. Recursive backtracking guarantees this because it visits every cell exactly once via DFS, creating a spanning tree.
DFS goes as deep as possible before backtracking. The algorithm keeps carving forward until it's surrounded by visited cells, creating long winding passages. If you prefer shorter, bushier passages, try Prim's algorithm.
Yes, for very large mazes (1000×1000+). The solution is to use an explicit stack data structure (iterative approach) instead of function call recursion. This removes the stack size limit entirely.