# [Tutor] exercise is recursion

**Remco Gerlich
**
scarblac@pino.selwerd.nl

*Tue, 21 Nov 2000 14:48:06 +0100*

On Mon, Nov 20, 2000 at 10:09:12PM -0600, Timothy Wilson wrote:
>* I thought I would write a little progam that would factor a given integer
*>* into its primes. This seemed like a good time to use recursion, but I'm
*>* having trouble making it work. Anyone see the problem here? I've added a few
*>* lines of debugging code, and there's a function to determine if a number is
*>* prime, but I don't think I'll need it. Any suggestions would be appreciated.
*>*
*>* --snip--
*>* #!/usr/bin/python
*>*
*>* # This python factors a number into its primes.
*>*
*>* from math import *
*
Ick, I hate import *.
>* def isPrime(number):
*>* for j in [2] + range(3, sqrt(number)+1, 2):
*>* if number in [1, 2]:
*>* return 1
*>* if number % j == 0:
*>* return 0
*>* return 1
*>*
*>* def factor(factors, number, i=2):
*>* while i < sqrt(number):
*>* if number % i == 0:
*>* factor(factors, number/i, i)
*>* factors.append(i)
*>* # if number/i == i:
*>* i = i + 1
*>* print str(number) + '\t' + str(i) + '\t' + str(factors) # debugging
*>* code
*>* return factors
*
I think the problem is that the while continues after you've found a factor,
and i is also increased after that. You should break after the append(i); any
other factors have already been found by the recursive call to factor().
Also, I think it should say <= not < in the while guard.
I would write it like this:
import math
def factors(n, highestsofar=2):
for i in range(highestsofar, math.sqrt(n)+1):
if n % i == 0:
return [i] + factors(n/i, i)
return [n]
I don't use a mutable list but add function results together because I
think that's a bit clearer. Instead of range(), you'd want to use a function
that only returns the primes in that range; you can adapt that from
Demo/scripts/primes.py in Python's source distribution. The highestsofar
variable is an optimization (you also use it).
Adding further optimization and unrolling it to an iterative version are
left as an excercise for the reader ;-).
--
Remco Gerlich