4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Note that if you use recursion you use a stack. I don't know that you can implement any graph traversal without an auxiliary data strcuture. $\endgroup$ – Raphael Oct 9 '16 at 20:06
  • 1
    $\begingroup$ Essentially "YES"; see web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf for the definition. Moreover, with a slight change, you get DFS ;) $\endgroup$ – Musa Al-hassy Oct 10 '16 at 16:11
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ can you elaborate more on MaxDepthDFS ? why are we checking if not DFS (G, s, depth) ? $\endgroup$ – gaurav5430 Feb 8 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.