Software bugs aren't inevitable

[Jerzy Karczmarczuk]

Steven D'Aprano recommends iteration over recursion:
> For instance, try these two simple functions for the nth number
> in the Fibonacci sequence:
> 
> def fibr(n):
>     "Recursive version of Fibonacci sequence."
>     if n == 0:  return 0
>     elif n == 1:  return 1
>     else:    return fibr(n-1) + fibr(n-2)
> 
> def fibi(n):
>     "Simple iterative version of Fibonacci sequence."
>     if n == 0:  return 0

etc.
> Try timing how long it takes to generate the 30th Fibonacci number
> (832040) using both of those algorithms. Now try the 50th. (Warning: the
> amount of work done by the recursive version increases at the same rate as
> the Fibonacci sequence itself increases. That's not quite exponentially,
> but it is fast enough to be very painful.)


First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity,
don't say such not-quite-truth as "not quite". But, what is more important:

If you don't know too much about the way the functional programming is
used nowadays, please refrain from giving nonsensical examples, since
NOBODY serious programs something in the style of your recursive version.
Such anti-advertizing of recursion says less about the recursion
than about yourself. Here you are a recursive version linear in n; it
returns the two last Fibonacci numbers of the sequence

def fibo(n):
      if n<2:
         return (n-1,n)
      else:
         (a,b)=fibo(n-1)
         return (b,a+b)

The exponential complexity, cascading version is a nice test case how to
use memoization, though, so it is not entirely senseless to learn it.

Jerzy Karczmarczuk