[Tutor] exercise is recursion

[Remco Gerlich]

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