3 ms·
Which is an odd example, since maze solving by recursion typically requires something like the Zipper data structure. And... no, that is not necessarily easier
by taeric 9y ago
Which is an odd example, since maze solving by recursion typically requires something like the Zipper data structure. And... no, that is not necessarily easier to deal with than just using a standard stack and jotting down your work as you go.
- deleted 9y ago[deleted]
- mysterydip 9y agoI 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.