Why is recursion so slow?

[Terry Reedy]

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