在遞歸條件滿足時返回值

Question

我正試圖在圖中查找遊覽。我寫了下面的代碼，這似乎是正確的打印行程。我希望它一旦找到第一個巡演並將巡迴作爲列表返回，就會停下來。然而，遞歸堆棧似乎完成了，我沒有得到想要的結果。當我找到第一個遊覽時，如何滿足我的條件，我該如何返回一個值並完全停止遞歸？謝謝。

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

代碼繼續尋找之旅，返回路徑後執行的原因是因爲它返回給調用是在迭代中通過邊緣進行的。如果在那裏沒有中斷或返回條件，則迭代繼續（並且遵循更多的遞歸調用）。

這裏是你的代碼的修改版本，返回到原來的調用（以及遞歸調用），一旦條件滿足，我增加了一些調試信息，試圖使這一過程更加清晰：

#!/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

當使用遞歸時，您需要將返回值傳遞迴整個調用堆棧。通常這不是使用遞歸的最佳方式。

沒有在你的代碼的細節去，這裏是一個快速的建議：

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