I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through a maze. Is there a way to do this just using the basic structure of recursive calls and base cases? Or will I need data structures such as queues or stacks to implement breadth-first recursion?
You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity.
If you look at virtually any description of BFS, e.g., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes
So, even if you aren't allowed to use some clearly-cut external queue data structure, you can easily embed one using node attributes:
def BFS(G, root): for each node in G: n.distance = inf n.parent = None n.next = None root.distance = 0 head = tail = root while head is not None: current = tail tail = tail.next for each node adjacent to current: if n.distance == inf: n.distance = current.distance + 1 n.parent = parent head.next = n head = head.next if tail is None: tail = head
Note that the above code is iterative, but it's trivial to make it recursive.
It's possible to run BFS recursively without any data structures, but with higher complexity. DFS, as opposed to BFS, uses a stack instead of a queue, and so it can be implemented recursively.
Suppose we modify DFS so that it takes a
MaxDepthDFS(G, s, max_depth)
It should perform DFS until it reaches the first unvisited node at
max_depth level, and returns whether it indeed found such a node. Then we could write the following variation of BFS:
def BFS(G, s): depth = 0 for i = 0, ..., |V|: if not DFS(G, s, depth) depth += 1
Again, note that the above code is iterative, but it's trivial to make it recursive.
Besides such (cheap) tricks, you cannot run BFS, as it uses a queue, and not a stack. Say, to the contrary, you have a recursive function
BFSVisit(G, s, current, more)
and consider the case where $s$ has $m$ neighbors. Then at the $m$th invocation,
more needs to carry $\omega(1)$ information, and thus is already a data structure.