Generating mazes using recursion
What is recursion?
Recursion is a programming concept where a function calls itself. While this sounds like an inifite loop, and if poorly written it can be, the function is designed to stop calling itself once its goal is reached.
function recursive()
{
if(goal_reached)
return;
recursive();
}
Why use recursion?
Recursion can be a useful way to break down certain complex problems into smaller, simpler pieces. It is also useful for iterating through complex data structures such as trees.
The power in recursion comes from its use of the call stack. Due to the recursive calls, the stack becomes a data structure in the algorithm, giving the code a way to keep track of, and get back to where it was. The downside of using the stack in this way is that most call stacks have a finite limit, so it is possible to overflow it if the algorithm recurses too far, so this must be kept in mind.
Using recursion to generate mazes
Maze generation is an excellent candidate for recursion. This complicated algorithm can be broken down into simpler pieces, just focusing on generating one cell at a time, and the call stack can be used to keep track of where the algorithm is in the maze, and how to get back. Here's how it works:
 Create a data structure to represent the maze. A two dimensional array works well. Each entry in the array represents a cell in the maze, and has properties to represent the state of the cell (whether it's been visited yet or not) and which walls it has.

Create a function that evaluates a cell.
 In order to evaluate a cell, pick one of the four walls randomly and see if the next cell beyond that wall has been evaluated.
 If it has not, then remove the wall and then recall this function to evaluate that cell. This is where the recursion happens, and where we use the call stack to trace our path through the maze.
 If the other cell has been evaluated, then move on to the next wall and evaluate its cell neighbor.
 Once all four walls have been evaluated, end the function (goal met). This is where we leverage the call stack to unwind our path through the maze.
Here is the pseudo Javascript code for this algorithm:
// Create a two dimensional array and initialize all cells to be unevaluated and have all four walls
let maze = createTwoDimensionalArray(WIDTH, HEIGHT, {evaluated: false, walls: NORTH  SOUTH  EAST  WEST});
// Call evaluateCell on the first cell
// Note that I start with the finish cell and work backwards, this way there is only one path leading to the finish
evaluateCell(WIDTH  1, HEIGHT  1);
// Recursive function to evaluate a single cell
function evaluateCell(x, y)
{
// Mark the cell as evaluated at the start so we don't circle back and get into an infinite loop
maze[x][y].evaluated = true;
// Pick a random wall to start evaluating and a random direction to continue the evaluation,
// this is what makes the maze random
let wall = pickRandomFromSet([NORTH, SOUTH, EAST, WEST]);
let direction = pickRandomFromSet([CLOCKWISE, COUNTERCLOCKWISE]);
// Iterate around each wall of the cell
for(let i = 0; i < NUMBER_OF_WALLS; i++, wall = getNextWall(wall, direction))
{
// Look at the neighbor cell beyond the wall and see if it has been evaluated yet
let neighbor = getNeighborCell(x, y, wall);
if(!neighbor.evaluated)
{
// If the neighbor cell has not yet been evaluated,
// then remove the wall between the cells
// and recursively call this function again to evaluate the neighbor call
clearWall(x, y, wall);
evaluateCell(neighbor.x, neighbor.y);
}
}
}
Questions and feedback
If you have any questions about using recursion for maze generation, or have any feedback on this article, please contact me. I'll try my best to answer your questions, and I value your feedback!