Software bugs aren't inevitable

[Steven D'Aprano]

On Wed, 14 Sep 2005 01:05:55 -0700, Paul Rubin wrote:

> There's a famous paper by John Hughes called "Why Functional
> Programming Matters" that (cheap oversimplification) says you should
> never modify the value of any variable.  So, no increments, not even
> for loops (use recursion instead).


Which works wonderfully as an academic exercise, but doesn't tend to work
so terribly well in the real world where the performance and
resource-requirement differences between iteration and recursion can be
significant.

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
    elif n == 1:  return 1
    else:
        Fn2 = 0
        Fn1 = 1
        for _ in range(2, n+1):
            s = Fn2 + Fn1
            Fn2, Fn1 = Fn1, s
        return s

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.)


-- 
Steven.