CODEWITHSUNDEEP
python
Shark Deng
Shark Deng

Reputation: 1088

Why the path variable cannot be returned?

I am using DFS to get all routes between two nodes.
enter image description here

My python code is as follows:

graph = {0: [1, 2, 3], 
         1: [3], 
         2: [0, 1], 
         3: []}
def DFS(start, stop, path=[], visited=[]):
    global count
    global result

    # add the visited node to path
    path.append(start)
    # mark this node visited to avoid infinite loop
    visited.append(start)

    # found
    if start == stop:
        print(path)

    else:
        # if not found
        values = graph.get(start)
        for next_ in values:
            # not visited node
            if not next_ in visited:
                DFS(next_, stop, path, visited)

    # remove the node from path and unmarked it 
    path.remove(start)
    visited.remove(start)

The problem is that if I print path in if start == stop, all 3 routes can be printed correctly. 

>>> DFS(2, 3)
[2, 0, 1, 3]
[2, 0, 3]
[2, 1, 3]

But if I change to return path in if start == stop, it would return nothing. 

def DFS(start, stop, path=[], visited=[]):
    global count
    global result

    # add the visited node to path
    path.append(start)
    # mark this node visited to avoid infinite loop
    visited.append(start)

    # found
    if start == stop:
        return path

    else:
        # if not found
        values = graph.get(start)
        for next_ in values:
            # not visited node
            if not next_ in visited:
                DFS(next_, stop, path, visited)

    # remove the node from path and unmarked it 
    path.remove(start)
    visited.remove(start)


>>> result = DFS(2, 3)
>>> result

Upvotes: 1

Views: 129

Answers (2)

Karl Knechtel
Karl Knechtel

Reputation: 61635

But if I change to return path in if start == stop, it would return nothing.

Right; because you got to this level of recursion from the previous one, which recursively called DFS(next_, stop, path, visited)... and ignored the result.

It is the same as if you called functions normally:

def inner():
    return "hello"

def outer():
    inner() # oops, it is not returned.

print(outer()) # None

In general you want to return the results from your recursive calls; but your case is a little special because you need to accumulate the results from multiple recursive calls (for next_ in values:). You could build a list and return it, but this is a bit tricky:

if start == stop:
    result = [path] # for uniformity, we need a list of paths in this case too.
    # Also, we can't `return` here, because we'll miss the cleanup at the end.
else:
    result = []
    values = graph.get(start)
    for next_ in values:
        # BTW, Python treats `not in` as a single operator that does
        # what we want here. It's preferred because it's easier to read.
        if next_ not in visited:
            # add results from the recursive call to our result.
            result.extend(DFS(next_, stop, path, visited))
            # it is `.extend` and not `.append` here because otherwise we will
            # build a tree of nested lists - do you understand why?
# Either way, we want to do our cleanup, and return the collected result.
path.remove(start)
visited.remove(start)
return result # important!

Tricky, right?

My preferred solution for these situations, therefore, is to write a recursive generator, and collect the results outside the recursion:

# Inside the function, we do:
if start == stop:
    yield path
else:
    values = graph.get(start)
    for next_ in values:
        if next_ not in visited:
            yield from DFS(next_, stop, path, visited))
path.remove(start)
visited.remove(start)

# Then when we call the function, collect the results:
paths = list(DFS(2, 3))
# Or iterate over them directly:
for path in DFS(2, 3):
    print("For example, you could take this route:", path)

(Also, the comment you received was good advice. Recursion is a lot easier to understand when you don't try to mutate the arguments and clean up afterwards. Instead, always pass those arguments, and when you make the recursive call, pass a modified version. When the recursion returns, cleanup is automatic, because you just go back to using the old object in the old stack frame.

Upvotes: 2

Gagan
Gagan

Reputation: 318

The problem with your code is that 

result=DFS(3,2)

will only return a valid result if start=stop which is not the case as 3!=2. To get the desired output you have to change the line

DFS(next_,stop,path,visited)

to

return DFS(next_,stop,path,visited)

Now whenever start gets equal to stop the path will be returned and this value will be propogated upwards

Upvotes: 0

Related Questions