I am trying to develop my intuition for recursion.
To this end I spent some time trying to solve mazes with recursive functions.
Along the way I discovered a hidden and dramatic universe, where collections of function calls band together, sacrificing whole family trees in the pursuit of a secure future for their species.
First, let’s solve some mazes:
Specifically, let’s start with this one, and use it as an example to develop a general strategy for solving mazes:
Right, tell me how to get from the entrance (always top left) to the exit (always bottom right).
Seems simple enough, just walk down until you hit the bottom, then go right. Piece of piss.
Ah but computers don’t work that way, they don’t like ambiguity. Try and be a bit more precise. Also what if the hedges in the maze are arranged differently? Does that plan still always work?
OK:
1) We already know where the exit is, so start there and work backwards, keeping track of where we’ve been, then we’ll have a nice ordered list of grid locations we need to traverse in order to get out of the maze.
2) Let’s try moving up first. Ah but then we hit a wall at the top.
3) No bother: move left
No no hold on this won’t do. This is all far too vague for a computer. At every step, it’s going to need very clear instructions to allow it to figure out what direction to go in.
SIGH… fine
Steps for the computer:
1) Go up if you can, and you haven’t come from that direction
2) Otherwise go right if you can, and you haven’t come from that direction
3) Otherwise go left if you can, and you haven’t come from that direction
4) Otherwise go down if you can, and you haven’t come from that direction
There! Happy!?!
Oh much better yes. How does it know how to stop though?
Ok shit. Before you do anything, check if you are at the entrance to the maze
🙂
This looks reasonably hopeful now. I’m pretty sure we’ve missed a few edge cases, but this looks like something we can work with.
(see below for my actual real notes I wrote while trying to figure out this strategy)
Bring on the Recursion
This process has the smell of something could be implemented using recursion.
We have a base case (‘am i at the entrance’), and some logic for deciding how to call the next iteration of the solution.
Oh blah blah blah recursion so what. Tell them about the Glarpols!
Oh fine… This is a Glarpol:
Don’t be put off by its cute and fuzzy appearance. It has a statistically tough challenge ahead of it.
Glarpols exist across infinite different parallel universes, with each universe looking suspiciously similar to our scrappily drawn mazes above.
Much like the Salmon has to struggle and swim upstream in order to spawn, and ultimately survive as a species, so too do the Glarpols.
In each universe, a solitary Glarpol is spawned at the exit to a randomly generated grid shaped maze. The exit is always on the bottom right of the grid, and the entrance is always on the top left of the grid.
If the Glarpol and its offspring manage to find a route to the entrance to the maze, they will survive as a species in this universe. If they do not, there will be no Glarpols in this particular universe.
In order to maintain their population, Glarpols require sufficient oxygen. Every time a Glarpol is created, they use a bit more oxygen.
If too many Glarpols are alive at the same time, then they will not have enough oxygen, and they will all die.
A Glarpol can move once, and breed once, and in contrast to many species, will stay alive until all of its children die, at which point it will also die.
Glarpols don’t know about the grid, but each Glarpol is born with the following information available to them:
1) Whether the maze has been solved by another Glarpol
2) Their ancestors’ journey up until this point
3) What the entrance to the maze looks like
4) Whether they are in a hedge
5) Whether they are in a wall
With this information, each solitary and freshly born Glarpol must decide what to do with their life. The choices are somewhat bleak…
-
Has someone else found a path? If so kill myself, I can’t help my species and I’m wasting oxygen.
-
Am I at the Entrance? If so tell the rest of my species that we are saved, and tell my parent how to get to the entrance. The effort of transmitting this message causes the me to die.
-
Am I in a Wall? If so kill myself, I can’t help my species and I’m wasting oxygen.
-
Am I in a Hedge? If so kill myself, I can’t help my species and I’m wasting oxygen.
If a Glarpol has managed to live long enough to get this point, they will give birth to three children, and immediately afterwards will send them out into the world, in all directions (left, right, up, down) other than the one which their parent (who they will never meet) came from. They will also give each of these children a copy of their ancestors’ journey up until this point, along with their current position.
The Glarpol will then patiently wait alone to hear back from their offspring about their fate.
If they hear back that one of their descendants has found the entrance to the maze, they happily forward on the message to their parent. As before, the effort required to do this causes them to die.
Otherwise, if their children die, they also die.
OK… weird story. Do you have some code I can see. This is recursion right?
That’s right. In this tenuous and painful analogy/metaphor, each spawned Glarpol is a recursive function call, oxygen is memory, and the path to the entrance of the maze is the solution to the maze.
If your program runs out of memory by calling too many recursive functions, it will crash. If it finds a path through the maze it terminates successfully.
If you want to see and/or play around with the Glarpols’ universe here is the code I developed when messing around with this idea:
https://github.com/robt1019/algorithms-etc.-/blob/master/glarpols.ts