[Tutor] recursive factoring
Jeff Shannon
jeff@ccvcorp.com
Thu, 17 Jan 2002 09:51:58 -0800
> alan.gauld@bt.com wrote:
>
> > def isPrime(n):
> >
> > 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)
>
> And if n%i != 0 what happens?
> And in either case what do we return? Nothing...
>
> Alan G
Yes, but we *are* appending to an outside (global?) list. If n%i !=0 then we want to ignore
the results (it's not a factor); if n%i == 0 then we *have* a factor and use a recursive call
to determine that factor's prime factors. So this function is, essentially, run only for
side effects. Probably not the clearest way of doing things, though. :)
Yet another example of why relying on side effects is poor practice, I guess....
Of course, if the original call is not made with a prime number, and relies upon that default
empty list, then you'll never get anything back from it. That 'return factors' statement is
only executed if n is prime, and the return values of the recursively called factor() are
never used anyhow.... so you're sort-of right, after all. It should work, though, if that
return statement is eliminated and factor() is called with an outside list, like so:
f = []
factor(42, f)
Jeff Shannon
Technician/Programmer
Credit International