2 ms·
I was thinking the classic case of a 2D array representing the maze: value of 1 for walls, 0 for space, 2 is the goal. Recursion of it is simple: Function Solv
by mysterydip 9y ago
I was thinking the classic case of a 2D array representing the maze: value of 1 for walls, 0 for space, 2 is the goal. Recursion of it is simple:
Function Solve(x,y,dir) {
Solved = false
If (maze[x,y] == 2) {
Print "goal at "+x+","+y
Return true
}
If ((dir != 3) && (maze[x,y-1] != 1)) { solved = Solve(x,y-1,1) }
If ((!solved) && (dir != 4) && (maze[x+1,y] != 1)) { solved = Solve(x+1,y,2) }
If ((!solved) && (dir != 1) && (maze[x,y+1] != 1)) { solved = Solve(x,y+1,3) }
If ((!solved) && (dir != 2) && (maze[x-1,y] != 1)) { solved = Solve(x-1,y,4) }
If (solved) {
Print "path "+x+","+y
}
Return solved
}
The pseudocode will search the maze, find the exit, then print its location followed by the path to get there in reverse order. Nothing complicated, but shows off the statefulness of recursion without needing anything else.
- taeric 9y agoAnd this is one where I find myself falling back onto (ironically, per the thread?) Dykstra's algorithm. Which I did not learn recursively. It makes much more sense because the "path" that I am recording is a first class thing in the algorithm and not a byproduct of the implementation.