Returning Through a Path

When the recursive search reaches the exit, it returns true. That true is passed back through the calls that led to the exit. Each call on the way back gets that true and returns it too, until it reaches the original call in hasPath. We are only answering whether a path exists, so this true is the answer.

Consider, for example, the following maze:

    0   1   2   3
  ┌───┬───┬───┬───┐
0 │ S │ • │ • │   │
  ├───┼───┼───┼───┤
1 │ █ │ █ │ • │ █ │
  ├───┼───┼───┼───┤
2 │ █ │ █ │ • │ E │
  └───┴───┴───┴───┘

In cell coordinates, the path from S to E is (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 3).

The call on (2, 3) sees the exit and returns true. At that moment the call stack holds one call for every cell on the path, with search(2,3) on top:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(2,3)  return true  (reached the exit) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌──────────────────────────────────────────────┐
        │ search(2,2)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(1,2)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,2)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,1)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,0)  waiting for a recursive call    │
        └──────────────────────────────────────────────┘

Then the call on (2, 2) has this expression:

return search(...) || search(...) || search(...) || search(...);

One of those recursive calls returned true, so the whole expression returns true. The top frame pops, and the call below it receives that true:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(1,2)  waiting for a recursive call ┃ ◀── receives true
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────────────┐
        │ search(0,2)  waiting for a recursive call │
        ├───────────────────────────────────────────┤
        │ search(0,1)  waiting for a recursive call │
        ├───────────────────────────────────────────┤
        │ search(0,0)  waiting for a recursive call │
        └───────────────────────────────────────────┘

The same thing happens at (0, 2), then (0, 1), then (0, 0). When the last frame returns, true reaches hasPath:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,0)  waiting for a recursive call ┃ ◀── receives true
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

Backing Out of a Dead End

Suppose the search steps onto a cell where every direction is blocked: each neighbor is a wall, off the edge, or already visited. Consider, for example, cell (0, 3) from our maze. The picture shows the maze with (0, 3) in brackets, and the visited array next to it:

    0   1   2   3             0   1   2   3
  ┌───┬───┬───┬───┐         ┌───┬───┬───┬───┐
0 │ S │   │   │[ ]│       0 │ x │ x │ x │ x │
  ├───┼───┼───┼───┤         ├───┼───┼───┼───┤
1 │ █ │ █ │   │ █ │       1 │   │   │   │   │
  ├───┼───┼───┼───┤         ├───┼───┼───┼───┤
2 │ █ │ █ │   │ E │       2 │   │   │   │   │
  └───┴───┴───┴───┘         └───┴───┴───┴───┘
        maze                     visited

The call stack when the search is on (0, 3) looks like this:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,3)  waiting for a direction to try  ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌──────────────────────────────────────────────┐
        │ search(0,2)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,1)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,0)  waiting for a recursive call    │
        └──────────────────────────────────────────────┘

The call on (0, 3) tries all four directions, and each one fails. All four recursive calls return false, so the || expression is false, and this call returns false as well. Returning false hands control back to the call that made it, which is the call on the previous cell, (0, 2).

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,2)  waiting for a recursive call    ┃ ◀── receives false
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌──────────────────────────────────────────────┐
        │ search(0,1)  waiting for a recursive call    │
        ├──────────────────────────────────────────────┤
        │ search(0,0)  waiting for a recursive call    │
        └──────────────────────────────────────────────┘

That call (search(0,2)) was partway through its own || expression. Now that the recursive call for one of its directions has returned false, it moves on to the next direction and tries that instead. If it also runs out of directions, it returns false, and control returns to the call on the cell before it.

In this case, search(0,2) will try going down to (1, 2), which eventually leads to the exit, so it will return true. This is the case we traced earlier, because (0, 2) is on the path to the exit.

So in this search, moving forward to a new cell is a recursive call, and moving back to the previous cell is a return from that call.

This strategy is called backtracking: The search goes forward as far as it can, and when it reaches a cell with no untried direction left, it tracks back to the most recent cell that still has one and continues from there. It keeps doing this until it either reaches the exit or has no earlier cell left to return to.