Can Breadth-First Search be Implemented Recursively without Data Structures?

Question

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?

Answer 1

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity.

---

Embedded-Queue Cheating

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 distance and parent.

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.

---

Higher-Complexity Simulation

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 max_depth parameter:

 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.