Is there a good way to exit a DFS procedure?

user_12597781 0
Viewed 807

I've learned that a recursive depth-first search procedure searches a whole tree by its depth, tracing through all possible choices.

enter image description here

However, I want to modify the function such that I can call a "total exit" in the middle, which will completely stop the recursion. Is there an efficient way to do this?

depth-first-search recursion algorithm
3 Answers

There are 3 ways to do this.

  1. Return a value saying you are done, and check for it after every call.
  2. Throw an exception and catch it at the top level.
  3. Switch from recursion to a stack and then break the loop.

The third is the most efficient but takes the most work. The first is the clearest. The second is simple and works..but tends to make code more complicated and is inefficient in many languages.

user_5854110

A common DFS works like this:

DFS(u){
    mark[u] = true
    for each v connected to u:
        if(!mark[v]) DFS(v)
}

You can try something like this:

static bool STOP = false;   

DFS(u){
    if(STOP) return;
    mark[u] = true
    for each v connected to u:
        if(!mark[v]) DFS(v)
}

placing a static bool in the beginning of the DFS should guarantee that nothing important will be done from now on with the stacked recursive calls of the DFS once you set STOP to true. Unfortunately it won't just ignore the function calls stacked, but they will finish immediatly.

user_53488750

coroutines

Billy's accepted answer presents a false trichotomy. There are more than three (3) ways to do this. Coroutines are perfectly suited for this because they are pausable, resumable, and cancellable -

def dfs(t):
  if not t:
    return                      # <- stop 
  else:
    yield from dfs(t.left)      # <- delegate control to left branch
    yield t.value               # <- yield a value and pause
    yield from dfs(t.right)     # <- delegate control to right branch

The caller has control over coroutines execution -

def search(t, query):
  for val in dfs(t):
    if val == query:
      return val        # <- return stops dfs as soon as query is matched
  return None           # <- otherwise return None if dfs is exhausted

Languages that support coroutines typically have a handful of other generic functions that makes them useful in a wide variety of ways

persistent iterators

Another option similar to coroutines is streams, or persistent iterators. See this Q&A for a concrete example.

user_6331830
Related