Think together · Start with a little story
A robot is exploring a maze. At each junction it chooses a path. When it reaches a dead end, it follows its task notes back to the junction and tries a direction it has not explored yet.
Lay out the process
- Enter a cellMark it visited
- Try a neighborExplore recursively
- Path is blockedReturn to the junction
- ContinueTry an unexplored direction
Recursion can express the idea of “exploring the paths near this position.”
A visited marker helps prevent going around a loop forever. If you record the current path, you may also need to update that path record when you backtrack, depending on the algorithm.
01Why is a maze related to recursion?
When you stand in a cell, you can think:
“I will move to a neighboring cell, then use the same method to continue searching for the exit from there.”
This turns the problem into a smaller problem of the same kind.
02What should you do at the current position?
Check for the exit
Have you reached the destination?
Mark the current position
Prevent returning to it repeatedly.
Try directions
Up, down, left, and right.
Return if it fails
Try another route.
03A simplified recursive model
bool dfs(int row, int col) {
if (at the exit) {
return true;
}
mark the current position as visited;
for (each of the four directions) {
if (the new position is open and unvisited) {
if (dfs(new position)) {
return true;
}
}
}
return false;
}This is C++-style pseudocode. Focus on understanding the process rather than memorizing a syntax template.
04How does the call stack change as you move in?
Moving into a new position is like entering a deeper function call.
05Why does a dead end “go back”?
If every direction from the current position is blocked, this call returns false.
Control goes back to the previous call, which tries the next direction.
This is the basic intuition behind backtracking.
06Why must you record where you have been?
A maze can contain loops.
If A leads to B and B leads back to A, without a visited record you might repeat:
07Is recursion always the fastest way through a maze?
No.
Recursive DFS is useful for questions like “Is there a path?” and for visiting all reachable positions. To find the shortest path in an unweighted graph, BFS is often a better fit.
The later “Search and Efficiency” topic will compare DFS and BFS directly.
What have you learned?
- A maze search can turn “find the exit from here” into “continue searching from the next position.”
- Entering a new position corresponds to a deeper call.
- When a path is blocked, returning to the previous call and trying another direction is the intuition behind backtracking.
- Record visited positions to avoid endlessly repeating a loop.
- Recursive DFS does not fit every search goal; shortest-path problems may use BFS.
Topic complete: The next topic is “Data Structures.”
Your turn to try
What could happen if a maze contains a loop and you never record which cells you have visited?
Ready? Open to see the explanation
The search may keep exploring the loop repeatedly. Define how visited states are recorded and when that record should be kept or undone.