returning none when it should be returning a list?

[John Machin]

On 1/05/2006 2:52 PM, randomtalk at gmail.com wrote:
> hello, i have another problem i feel that i have to be missing
> something.. Basically, i've written a recursive function to find all
> the prime up to a number (lim).. here is the function:
> 
> The function basically takes in a list of all the prime number found,
> it takes the next number to be tested for (next) and the limit it will
> go up to. It divide next by the list of previous prime numbers if next
> is not bigger than lim, count up all the times where it's not evenly
> divdided, if the result is equal the length of prime number, then we
> have another prime number, lather rinse and repeat :)
> 
> def findPrime(seed, next, lim):
>     print("seed: " + str(seed) + " next: " + str(next) + " lim: " +
> str(lim))
>     print(seed)
>     if(next >= lim):
>         print(seed)
>         return seed
>     else:
>         count = 0;
>         for num in seed:
>             modu = math.modf(float(next)/float(num));
>             if(modu[0] > 0):
>                 count += 1
>         if(count == len(seed)):
>             seed.append(next)
>             findPrime(seed, next+2, lim)
>         else:
>             findPrime(seed, next+2, lim)
> 
> As you can probably see, i've printed the value of seed up until the
> point where i'm returning the seed, however, the function still returns
> None..
> 

That's because it "falls off the end" of the function, which causes it 
to return None. However that's not your only problem. Major other 
problem is updating "seed" in situ.

Consider the following:

=== file: pseed.py ===
def findPrime(seed, next, lim):
     print "seed: %r, next: %d, lim: %d" % (seed, next, lim)
     if next >= lim:
         return seed
     for num in seed:
         # modu = math.modf(float(next)/float(num));
         # Try integer arithmetic:
         if num > 2 and not (next % num):
             # "next" is not a prime number
             return findPrime(seed, next+2, lim)
     return findPrime(seed + [next], next+2, lim)

# results:
"""
 >>> pseed.findPrime([1, 2], 3, 30)
seed: [1, 2], next: 3, lim: 30
seed: [1, 2, 3], next: 5, lim: 30
seed: [1, 2, 3, 5], next: 7, lim: 30
seed: [1, 2, 3, 5, 7], next: 9, lim: 30
seed: [1, 2, 3, 5, 7], next: 11, lim: 30
seed: [1, 2, 3, 5, 7, 11], next: 13, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 15, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 17, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17], next: 19, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 21, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 23, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 25, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 27, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 29, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29], next: 31, lim: 30
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
 >>>
"""

# Doh! Looks like recursion not necessary. Google 'eliminate tail 
recursion' :-)

def findPrime2(lim):
     seed = [1, 2]
     for next in xrange(3, lim, 2):
         prime = True
         for num in seed:
             if num > 2 and not (next % num):
                 prime = False
                 break
         if prime:
             seed.append(next)
     return seed

# results:
"""
 >>> pseed.findPrime2(30)
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
 >>>
"""