Why is recursion so slow?
Terry Reedy
tjreedy at udel.edu
Sun Jun 29 07:27:50 CEST 2008
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
More information about the Python-list
mailing list