Returning value when condition met in recursion

Question

I am trying to find tours in a graph. I have written the following code, this seems to be printing tours correctly. I want it to stop once it have found the first tour and return the tour as a list. However, the recursion stack seems to finish to completion and I am not getting the desired result. How can I return a value and fully stop the recursion when I find the first tour i.e. my condition is met? Thanks.

def get_tour(start, graph, path):
    if path==[]:
        from_node=start
    else:
        from_node=path[-1][1]

    if graph==[]:
        if start in path[-1]:
            print "Tour Found"
            return path

    else:
        edges=[node for node in graph if from_node in node]
        for edge in edges:
            to_node=[i for i in edge if i<> from_node][0]
            p=list(path)
            p.append((from_node,to_node))            
            g=list(graph)
            g.remove(edge)
            get_tour(start, g,p)


g=[(1,2), (1,3), (2,3)]

get_tour(1, graph=g, path=[])

Answer 1

The reason the code continues to execute after finding the tour and returning the path is because it returns it to the call that was made within the iteration through the edges. If there is no break or return condition there then the iterations continue (and more recursive calls are followed).

Here is an amended version of your code that returns to the original call (as well as the recursive call) as soon as the conditions are satisfied, I have added some debug information to try to make the process clearer:

#!/usr/bin/python

# globals
verbose = True

def get_tour(start, graph, path):
    if path==[]:
        from_node=start
    else:
        from_node=path[-1][1]

    if verbose:
        print '\nfrom_node:\t', from_node
        print 'start:\t', start
        print 'graph:\t', graph
        print 'path:\t', path

    if graph==[]:
        if start in path[-1]:
            print "Tour Found"
            return path

    else:
        edges=[node for node in graph if from_node in node]
        for edge in edges:
            to_node=[i for i in edge if i <> from_node][0]
            p=list(path)
            p.append((from_node,to_node))            
            g=list(graph)
            g.remove(edge)
            path = get_tour(start, g, p)
            if path:
                return path


g=[(1,2), (1,3), (2,3)]

get_tour(1, graph=g, path=[])

Answer 2

When using recursion you need to pass back the return value up to the whole call stack. Normally this isn't the best way to use recursion.

Without going in the details of your code, here is a quick suggestion:

def get_tour(start, graph, path):
    ret_val = None
    # Some code..
    if graph==[]:
        # Some code..
    else:
        edges=[node for node in graph if from_node in node]
        for edge in edges:
            # Some more code..
            ret_val = get_tour(start, g,p)
            if ret_val:
                break
    return ret_val