slix wrote:
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?
The comparison below has nothing to do with recursion versus iteration.
(It is a common myth.) You (as have others) are comparing an
exponential, O(1.6**n), algorithm with a linear, O(n), algorithm.
def fibr(nbr):
if nbr > 1:
return fibr(nbr-1) + fibr(nbr-2)
if nbr == 1:
return 1
if nbr == 0:
return 0
This is exponential due to calculating fib(n-2) twice, fib(n-3) thrice,
fib(n-4) 5 times, fir(n-5) 8 times, etc. (If you notice an interesting
pattern, you are probably correct!) (It returns None for n < 0.)
If rewritten as iteratively, with a stack, it is still exponential.
def fibf(n):
sum=0
a=1
b=1
if n<=2: return 1
for i in range(3,n+1):
sum=a+b
a=b
b=sum
return sum
This is a different, linear algorithm. fib(i), 0<=i<n, is calculated
just once. (It returns 1 for n < 0.) If rewritten (tail) recursively,
it is still linear.
In Python, an algorithm written with iteration is faster than the same
algorithm written with recursion because of the cost of function calls.
But the difference should be a multiplicative factor that is nearly
constant for different n. (I plan to do experiments to pin this down
better.) Consequently, algorithms that can easily be written
iteratively, especially using for loops, usually are in Python programs.
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
