Python recursion behaving weirdly

Question

I am writing the following program in python:

def find_graph(graph, start, end, path=[]):
    f=0
    if start==end:
        if start in graph:
            return start
    if not start in graph:
        return None
    if not end in graph.values():
        return None
    path.append(start)
    for i in graph[start]:
        if end in graph[start]:
            path.append(end)
            f=1
            break

        else:
            for j in graph[start]:
                if f==1:
                    break
                else:
                    find_graph(graph, j, end, path)


    return path

p=find_graph({'A': ['B','C'], 'B': ['C', 'D'], 'C': 'D', 'D': 'E'}, 'A', 'E')
print(p)

It isn't complete yet, but I just want to know, when it's in its last step, i.e., it does path.append('E'), then it does f=1 and break. Then it goes to the return path line; next it should return this value, but instead it goes to find_graph(graph, j, end, path) line in the else condition. Why is this happening? I put the f flag also, just so that it doesn't do this, but the moment it comes to return path f becomes 0, I don't know why. Please help.

The problem is that, once you find a path with the recursive call, you don't leave the loop. Rather, you keep going to find all legal paths ... but you never backtrack, so the solution is far too long. — Prune, Oct 17 '16 at 17:44
@Prune How do I leave the loop then? And could you explain backtracking in python please? — Shek, Oct 17 '16 at 17:56
Backtracking in a graph search is explained in many places on line. What didn't you understand? Covering it all here is well beyond the scope of StackOverflow. — Prune, Oct 17 '16 at 21:39
@Daniel Roseman ... This is not a problem from failing to return a value: the function communicates by stuffing everything into **path**. When the program finally returns after exhausting all possibilities, **path** contains an over-abundance of search history. Voting to reopen ... — Prune, Oct 17 '16 at 21:44
As an aside: Independent of the function's internal workings, using an empty list as default argument (`path=[]`) might get you in trouble (though not in your test above): https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument/1133013 — sebastian, Oct 18 '16 at 06:20

score 0 · Answer 1 · answered Nov 25 '18 at 00:32

It's been a couple of years, so let's solve this. The f flag variable is set to 1 just before the function returns so the test f == 1 is never true. This also seems to be a problem:

if not end in graph.values():
    return None

as an end node 'F' could be in 'B': ['C', 'D', 'F'], and have no children but the above would fail even though the graph is valid. The graph is complicated by having two different structures for children:

'B': ['C', 'D'], 'C': 'D',

instead of simply:

'B': ['C', 'D'], 'C': ['D'],

But we can work with that. Finally, you're not finding a graph, or a path through a graph, but rather all the paths through a graph so we need different names and to make sure we're always returning a list of lists (or empty list):

def find_paths(graph, start, end):

    if start not in graph:
        return []

    if start == end:
        return [[start]]

    nodes = list(graph[start])

    if end in nodes:
        return [[start, end]]

    paths = []

    for node in nodes:
        for sub_path in find_paths(graph, node, end):
            paths.append([start] + sub_path)

    return paths

print(find_paths({'A': ['B', 'C'], 'B': ['C', 'D'], 'C': 'D', 'D': 'E'}, 'A', 'E'))

OUTPUT

> python3 test.py
[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'E']]
>

We can see that there are three paths from 'A' to 'E' -- and that the code is simpler than you tried to make it.

Python recursion behaving weirdly

1 Answers1