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]

Answer 2

A more functional-style version.

def prime_factorize( number ):
    def recurse( factors, x, n ):
        if x<2: return factors # 0,1 dont have prime factors
        if n > 1+x**0.5: # reached the upper limit
            factors.append( x ) # the only prime left is x itself
            return factors
        if x%n==0: # x is a factor
            factors.append( n )
            return recurse( factors, x/n, n )
        else:
            return recurse( factors, x, n+1 )
    return recurse( [], number, 2)

for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
    assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
    #print num, ":", factors

Answer 3

@Anthony's correctly answered your original question about print. However, in the spirit of the several tips that were also offered, here's a simple refactorization using tail recursion removal:

def prime_factorize(x):
  li = []
  while x >= 2:
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
      if not x%i:
        li.append(i)
        break
    else:
      li.append(x)
      return li
    x //= i

This doesn't address the crucial performance issues (big-O behavior is the same as for your original solution) -- but since Python itself doesn't do tail-recursion optimization, it's important to learn to do it manually.

"Change the [non-base-case] recursive steps 'return thisfun(newargs)' into args=newargs; continue and put the whole body into a while True: loop" is the basic idea of tail-recursion optimization. Here I've also made li a non-arg (no reason for it to be an arg), put a condition on the while, and avoided the continue since the recursive step was at the end of the body anyway.

This formulation would be a good basis from which to apply further optimizing refactorings (sqrt avoidance, memoization, ...) to reach towards better performance.