[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