[Tutor] recursive factoring

[Jeff Shannon]

> 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