Recursion and Generators

[David Eppstein]

In article <b4a8ffb6.0407101006.567e82eb at posting.google.com>,
 tkpmep at hotmail.com (Thomas Philips) wrote:

> I'm totally comfortable with it backing up levels, yielding a new
> result each time. It is intuitive to me that at each level it should
> yield a list followed by a StopIteration. What is not clear to me is
> why it feels an uncontrollable urge to descend through the list of
> nested calls to testRecursion one last time after it has come up to
> the highest level and yielded [1,2,3,4] StopIteration.

After it has yielded at the top level, all of your recursive for-loops 
are still looping, and won't stop looping until each generator has been 
activated again and has raised a StopIteration.

E.g. consider the following greatly-simplified example

def gen():
    yield 17

for x in gen():
    print x

What actually happens here:

Loop setup:
gen() is called and creates a generator g.  g is not called yet.

First iteration of loop:
g is called for the first time and yields 17.  Execution of g is 
suspended within the yield statement.  17 is printed.

Second iteration of loop:
g is called for the second time; execution of g is continued after the 
yield statement.  Since there is nothing left of g, it raises 
StopIteration.  The exception causes the for loop to exit.


In your recursive example, the state of the generators "after it has 
come to the highest level and yielded [1,2,3,4]" is the same as in this 
smaller example between the first and second iterations: the generators 
are all suspended within their yield statements.  You need to call into 
them again to get them to raise StopIteration.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science