Scope of Python Recursive Generators

Question

Hey all, I was working on a recursive generator to create the fixed integer partitions of a number and I was confused by a scoping issue.

The code is similar to this snippet.

def testGen(a,n):
    if n <= 1:
        print('yield', a)
        yield a
    else:
        for i in range(2):
            a[i] += n
            for j in testGen(a,n-i-1):
                yield j

My confusion is illustrated below.

>>> list(testGen([1,2],4))
yield [10, 2]
yield [10, 4]
yield [10, 7]
yield [12, 11]
yield [12, 13]
[[12, 13], [12, 13], [12, 13], [12, 13], [12, 13]]

I can get the right answer simply by using a copy of the array (e.g. passing in a[:] to the recursive call) but I still don't understand the above behavior. Why are the print statements and yield values different?

Answer 1

I would guess you are mutating the array, so when you print it has a particular value, then the next time you print it has actually updated the value, and so on. At the end, you have 5 references to the same array, so of course you have the same value 5 times.

Answer 2

The print statement displays the list at that particular point in time. Your code changes the list as you run it, so by the time you examine the list at the end, you see its value then.

You can observe this by stepping through:

>>> g = testGen([1,2],4)
>>> g.next()
('yield', [10, 2])   # note brackets in print statement because I'm on python 2.5
[10, 2]
>>> g.next()
('yield', [10, 4])
[10, 4]
>>> g.next()
('yield', [10, 7])
[10, 7]
>>> g.next()
('yield', [12, 11])
[12, 11]
>>> g.next()
('yield', [12, 13])
[12, 13]

Answer 3

The print and yield statements are different because you only have one print statement while you have 2 yields. Try this:

def testGen(a,n):
    if n <= 1:
        print('yield', a)
        yield a
    else:
        for i in range(2):
            a[i] += n
            for j in testGen(a,n-i-1):
                print('yield', j)
                yield j

>>> list(testGen([1,2],4))
('yield', [10, 2])
('yield', [10, 2])
('yield', [10, 2])
('yield', [10, 2])
('yield', [10, 4])
('yield', [10, 4])
('yield', [10, 4])
('yield', [10, 4])
('yield', [10, 7])
('yield', [10, 7])
('yield', [10, 7])
('yield', [12, 11])
('yield', [12, 11])
('yield', [12, 11])
('yield', [12, 13])
('yield', [12, 13])
('yield', [12, 13])
[[12, 13], [12, 13], [12, 13], [12, 13], [12, 13]]

You will see that the last yields are your answers because you've been passing around the same list instead of making a copy.

Answer 4

Lists are mutable objects, if you pass in a list, and the generator performs in-place operations on that list, then finally all references to the list will point to the same list.