Recursion and Generators

[Michael Sparks]

On 9 Jul 2004, Thomas Philips wrote:
...
> However, it then calls testRecursion recursively a second time (see
> the sequence of calls below), and of course no results are yielded
> this time around.

Results are yielded, but obviously aren't what you're expecting.

The sequence of values yielded (or raised) by testRecursion(1) is:
  [1], StopIteration

Thus:
>>> print list(testRecursion(1))
[[1]]

testRecursion(2) goes into a loop that says:

For every value yielded by testRecursion(1)
   * Take that value, add [2]
   * yield that value

However testRecursion(1) only yields one value - [1] . Since
testRecursion(2) yields one value for every value testRecursion(1) yields,
testRecursion(1) yields one value.

Specifically the values it yields or exceptions it raises are:
  [1,2], StopIteration

Likewise testRecursion(3) yields one value for every value that
testRecursion(2) yields - specifically it appends 3 onto every value
yielded by testRecursion(2). Since testRecursion(2) yields just one value,
testRecursion(3) yields just one value before it's own StopIteration
exception.

Bear in mind that your loop of for x in generator: says "for every value
returned by the generator", peform this loop. Since the base case only
yields one value, every other generator in that form of recursion returns
one value. (You could probably easily do a proof by induction for this
behaviour)

If you're having problems seeing this, consider this slight modification
to your recursive generator:
>>> def testRecursion(n):
...     if n == 1:
...         yield [1]
...     else:
...         yield [ x for x in testRecursion(n-1) ]+[n]
...
>>> print list(testRecursion(1))
[[1]]
>>> print list(testRecursion(2))
[[[1], 2]]
>>> print list(testRecursion(3))
[[[[1], 2], 3]]
>>> print list(testRecursion(4))
[[[[[1], 2], 3], 4]]

As you can see, clearerly there is 1 value being generated for every value
yielded by the previous generator here.

Hope that makes things clearer!


Michael.