How to stop recursion after finding solution / return-CodePudding

I have a problem with my recursion function and hope to get help here.

I wanted to write a function where all paths between two nodes are found, where the function should stop after finding a solution and output the first path. If this path has already been found, the function should continue until it finds the next path and stop there again and output the found path.

For this I wrote a function (or I intended to) that it starts in the start node, then to its neighbor node, and then to the neighbor node of the neighbor node etc. until the end node is reached. Then it should output the path. If the end node is not reached, it should delete the last node and continue there. So a kind of DFS algorithm with backtracking.

My problem is that the function does not stop after it has found the end node. I assume that it is because there are still functions "open" that need to be closed. If I write "return pathfind(nknots)" instead of just "pathfind(nkots)" at the bottom of my code, then my code stops upon reaching the end node but does not continue with backtracking if the end node has not yet been reached. So in both cases I have a problem.

Does anyone maybe have an idea how I can solve the problem ? Preferably in a way that I don't have to change my own code/idea too much ?

def pathfind(x):                   
                        
   visited.add(x)
        
   if neighbours[x] != {}:

        for nknots in neighbours[x]:

            if nknots == n:
                
                print("final node is found")
                augpath.append(n)
                return augpath
            
            elif nknots in augpath or nknots not in neighbours or nknots in visited:
                
                print("Node already in augpath, visited or has no neighbours: ")
                continue
                        
            else:       
                augpath.append(nknots)

                pathfind(nknots)  # pathfind on new node

                visited.remove(nknots) 
                augpath.pop()

CodePudding user response：

If you want the function to stop as soon as it encounters the end node, and return the path, then you should use the return statement to tell it to stop:

def onepath(start, end, neighbours, path=[], visited=None):
    if visited is None:
        visited = {start}
    if start == end:
        return path   [start]
    else:
        for n in neighbours[start]:
            if n not in visited:
                visited.add(n)
                p = onepath(n, end, neighbours, path   [start], visited)
                if p:
                    return p
        return None

If you want to find all paths, then you should return a list made of all the paths found by all the recursive calls:

def allpaths1(start, end, neighbours, path=[], visited=set()):
    if start == end:
        return [path   [start]]
    else:
        return [p
            for n in neighbours[start]
            if n not in visited
                for p in allpaths1(n, end, neighbours, path   [start], visited | {start})
        ]

Note that the syntax for a list comprehension with double for is a bit awkward. For these kinds of functions, I think the most pythonic way is to use generators, rather than lists:

def allpaths2(start, end, neighbours, path=[], visited=set()):
    if start == end:
        yield path   [start]
    else:
        for n in neighbours[start]:
            if n not in visited:
                yield from allpaths2(n, end, neighbours, path   [start], visited | {start})

neighbours = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2, 4], 4: [1, 3]}
# 1 - 2
# | \ |
# 4 - 3

print(onepath(1, 3, neighbours))
# [1, 2, 3]

print(allpaths1(1, 3, neighbours))
# [[1, 2, 3], [1, 3], [1, 4, 3]]

print(list(allpaths2(1, 3, neighbours)))
# [[1, 2, 3], [1, 3], [1, 4, 3]]