[Tutor] recursive factoring

[Tim Wilson]

Hi everyone,

I've been trying to write a little function that will generate a list of
all the prime factors of a given integer. This seems like the sort of
problem that maps very well to a recursive algorithm. Take the prime
factors of 24 for example:

  24
 /  \
2    12
    /  \
   2    6
       / \
      2   3

The prime factors are 2, 2, 2, and 3. If that isn't recursion waiting to
happen, I don't know what is. :-)

Unfortunately, I can't get my function to work. I just don't grok
recursion. Here's what I've tried (one version of it anyway):

import math

def isPrime(n):
    if n in [1, 2]: return 1
    for i in [2] + range(3, math.sqrt(n)+1, 2):
        if n % i == 0:
            return 0
    return 1

def factor(n, factors=[]):
    if isPrime(n):
        factors.append(n)
        return factors
    else:
        for i in range(2, math.sqrt(n)+1):
            if n % i == 0:
                factor(n/i, factors)

This is quite broken (it returns 'None'), but I hope you can see where I
was headed.

Any suggestions?

-Tim

--
Tim Wilson      |   Visit Sibley online:   | Check out:
Henry Sibley HS |  http://www.isd197.org   | http://www.zope.com
W. St. Paul, MN |                          | http://slashdot.org
wilson@visi.com |  <dtml-var pithy_quote>  | http://linux.com