[Tutor] recursive factoring
mikalzet@libero.it
mikalzet@libero.it
Thu, 17 Jan 2002 18:38:20 +0100 (CET)
On Thu, 17 Jan 2002, Kirby Urner wrote:
> This could also be written recursively:
>
> def factor(n):
> if n==1: return []
> b = 2
> while b <= n:
> while not n%b:
> return [b] + factor(n/b)
> b += 1
> return a
> I should do some profiling to get actual time
> comparisons. This one is probably faster up to
> a point, then the sieve would overtake it.
It would be interesting to find out. I recently faced a similar problem
with the fibonacci() function taken from "Learning how to think like a
Computer Scientist with Python".
The first fibonacci() function the text suggests is
def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n-1) + (fibonacci(n-2)
this function calculates fibonacci(30) in a preceptible time, and
fibonacci(40) takes pretty long on my system.
Later in the text a different method is suggested:
previous = {0:1L, 1:1L}
def fibonacci(n):
if previous.has_key(n):
return previous(n)
else:
newValue = fibonacci(n-1) + fibonacci(n-2)
previous[n] = newValue
return newValue
Now fibonacci(40) is practically instantaneous.
This is much faster; however calculation of fibonacci much greater than
500 is impossible first go. To calculate fibonacci(100000) you have to
first build the dictionary in approximately 500-large steps, i.e.
after calcualting fibonacci(500) it becomes possible to calcualte
fibonacci(1000), it now becomes possible to calculate fibonacci(1500) and
so on.
So I wrote a non-recursive function like this:
def fibonacci(n):
a = 1L
b = 1L
if n < 2: return 1
else:
z=2
while z <= n:
c = a + b
a, b = b, c
z = z + n
return c
This function seems at least as fast as the previous one, but there is a
big difference: fibonacci(100000) is possible first go (it takes looong
seconds and the result is a number of over 20000 digits if I well
remember).
This makes me think that perhaps for this sort of chore recursion is
not as efficient as direct calculation methods.
I wander: are there any guidelines as to when recursion is more / less
efficient than other methods ? (One could avoid struggling to invent one
type of solution in situations where other types of solution are known to
be more efficient).
--
Michele Alzetta