Python Recursive Scope Issue

Question

Yesterday, I made a Sieve of Eratosthenes to generate prime numbers and ran into a little weirdness that I can't really figure out.

My original code looked like this:

def generate(n, p=2, primes=[2], composites=set()):
    numbers = [i for i in range(p + 1, n + 1) if i % 2 != 0]
    composites = composites.union({p * i for i in range(p ** 2, n)})
    for i in numbers:
        if i > p and i not in composites:
            primes.append(i)
            return generate(n, i, primes, composites)
    else:
        return primes

But, with successive calls, this happens:

>>> generate(5)
[2, 3, 5]
>>> generate(5)
[2, 3, 5, 3, 5]
>>> generate(5)
[2, 3, 5, 3, 5, 3, 5]
>>> generate(5)
[2, 3, 5, 3, 5, 3, 5, 3, 5]

So it adds [3, 5] every call. It appears that the 'primes' list is in scope after successive calls to the generate function.

I fixed it by passing a copy of the list when the function recurses.

    if i > p and i not in composites:
        return generate(n, i, primes + [i], composites)

Anybody know what is happening here?

@Kevin - not a dupe of that because the argument is passed, not using the default — mhlester, Jan 10 '14 at 17:10
And to further what Kevin said, it's the default set that is passed explicitly to the recursive calls. — chepner, Jan 10 '14 at 17:12

score 1 · Answer 1 · answered Jan 10 '14 at 17:03

1

Because you pass it through the function argument, the independent scope of each function is pointing to the same data. Mutating one of them mutates it everywhere.

answered Jan 10 '14 at 17:03

mhlester

22,781
10
52
75

Python Recursive Scope Issue

1 Answers1