[Tutor] Recursion doubt

[Anshu Raval]

Hi, 
At the url http://www.python.org/doc/essays/graphs.html there is some code by Guido Van Rossum for computing paths through a graph - I have pasted it below for reference - 
Let's write a simple function to determine a path between two nodes. It takes a graph and the start and end nodes as arguments. It will return a list of nodes (including the start and end nodes) comprising the path. When no path can be found, it returns None. The same node will not occur more than once on the path returned (i.e. it won't contain cycles). The algorithm uses an important technique called backtracking: it tries each possibility in turn until it finds a solution. 
    def find_path(graph, start, end, path=[]):         path = path + [start]         if start == end:             return path         if not graph.has_key(start):             return None         for node in graph[start]:             if node not in path:                 newpath = find_path(graph, node, end, path)                 if newpath: return newpath         return None 
*** He then says------------------------ 
It is simple to change this function to return a list of all paths (without cycles) instead of the first path it finds: 
    def find_all_paths(graph, start, end, path=[]):         path = path + [start]         if start == end:             return [path]         if not graph.has_key(start):             return []         paths = []         for node in graph[start]:             if node not in path:                 newpaths = find_all_paths(graph, node, end, path)                 for newpath in newpaths:                     paths.append(newpath)         return paths 
*** I couldn't understand how it was simple to change the function find paths to find all paths. How would you think about writing this second function recursively. Especially the part about if start==end: return [path]. I feel you would give square brackets around path here after first writing the inductive part ... for node in graph[start] .... and then by trial and error put square brackets around path in the Basis part. Can someone please explain how to write this code. Thanks! 
_________________________________________________________________
Video: Get a glimpse of the latest in Cricket, Bollywood, News and Fashion. Only on MSN videos.
http://video.msn.com/?mkt=en-in
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20080415/6acb0338/attachment-0001.htm