Cannot understand the detailedly the following code

[Gabriel Genellina]

En Tue, 08 Apr 2008 09:45:35 -0300, A.T.Hofkamp <hat at se-162.se.wtb.tue.nl>  
escribió:

> On 2008-04-08, reachmsn at hotmail.com <reachmsn at hotmail.com> wrote:
>
> [deleted a long piece of text by our BDFL about recursive graph  
> path-finding algorithm]
>
>> 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!
>
> The same as any other function.
> (the trick with recursive functions is not to think about recursion.  
> Instead,
> pretend you are calling another function that happens to have the same  
> name.)

But our BDFL played some tricks to make both functions look more similar  
than they would instead. Take the "single path" variant:

     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

Why are those "return None" there, if not to be replaced by "return []"?  
Nobody writes that final one at least. Anyway, using the current Python  
version, it's easier to mutate the above function into a generator of all  
posible solutions; I hope the OP finds the mutation easier to follow:

def find_all_paths(graph, start, end, path=[]):
         path = path + [start]
         if start == end:
             yield path
             return
         if start not in graph:
             return
         for node in graph[start]:
             if node not in path:
                 for newpath in find_all_paths(graph, node, end, path):
                     yield newpath

The last two lines might be replaced in Python 3 by:
yield *find_all_paths
if this patch is accepted: http://bugs.python.org/issue2292

-- 
Gabriel Genellina