Python recursive program to prime factorize a number

Question

I wrote the following program to prime factorize a number:

import math
def prime_factorize(x,li=[]):
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
        if not x%i:
            li.append(i)
            break
    else:                      #This else belongs to for
        li.append(x)
        print li               #First print statement; This is what is returned
        return li
    prime_factorize(x/i,li)

if __name__=='__main__':
    print prime_factorize(300)   #Second print statement, WTF. why is this None

Following is the output I get:

 [2, 2, 3, 5, 5]
 None

Altho', the returned value is printed properly, the after returned value seems to be printing none, all the time. What am I missing?

Also, how can I improve the program (continuing to use the recursion)

Answer 1

Your prime_factorize function doesn't have a return statement in the recursive case -- you want to invoke "return prime_factorize(x/i,li)" on its last line. Try it with a prime number (so the recursive call isn't needed) to see that it works in that case.

Also you probably want to make the signature something like:

def prime_factorize(x,li=None):
    if li is None: li = []

otherwise you get wrong results when calling it two or more times:

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]