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)

Solution 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]

Solution 2

If you want to do it completely recursive, I'd recommend this code, it does return the correct answer and the way it works is pretty clear. If you want to make the program as efficient as possible I'd recommend you to stick to one of your previous methods.

def primeFact (i, f):
    if i < f:
        return []
    if i % f == 0:
        return [f] + primeFact (i / f, 2)
    return primeFact (i, f + 1)

This is a completely recursive way of solving your problem

>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]

Solution 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.

Solution 4

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

View more solutions