The only difference between an iterative depth-first search and an iterative breadth-first search is that a DFS uses a stack to keep track of which nodes to search next and a BFS uses a queue. Due to the use of a stack, a recursive implementation of a DFS is quite simple, since the call stack essentially doubles as the frontier. A recursive BFS, on the other hand, often doesn't make sense. To that end, I would like to try a number of experiments with allowing pieces of code to be placed into a call queue rather than a stack, with the benchmark being that using this to create a recursive BFS is essentially the same as creating a recursive DFS.
Some things to note:
- This is probably best accomplished either by having some type of subscope that modifies function call behavior inside it, or via some form of a Go-style
defer-like system.
- Generally during execution, conceptually, calling a function can be thought of as placing the contents of that function onto a stack, and executing an instruction can be thought of as popping the top of the stack. This makes thinking of how a queue would work relatively simple, with one major issue: Return values. With a stack, the code that uses the values returned is next to where they are returned from. With a queue, they're, potentially at opposite ends of the execution chain. How this should work, especially in a way that allows queued recursion to work, is the biggest problem at the moment.
- The queuing needs to reach across the recursion. In other words, queuing a function inside of a recursive call needs to place the newly queued function into the same queue as the call it was made from. The simplest way to do this is probably to provide a way to create a named queue such that when a function is enqueued the user can specify onto which queue it is placed.
The only difference between an iterative depth-first search and an iterative breadth-first search is that a DFS uses a stack to keep track of which nodes to search next and a BFS uses a queue. Due to the use of a stack, a recursive implementation of a DFS is quite simple, since the call stack essentially doubles as the frontier. A recursive BFS, on the other hand, often doesn't make sense. To that end, I would like to try a number of experiments with allowing pieces of code to be placed into a call queue rather than a stack, with the benchmark being that using this to create a recursive BFS is essentially the same as creating a recursive DFS.
Some things to note:
defer-like system.