Software bugs aren't inevitable

[Terry Reedy]

"Steven D'Aprano" <steve at REMOVETHIScyber.com.au> wrote in message 
news:pan.2005.09.14.18.39.09.585065 at REMOVETHIScyber.com.au...
> On Wed, 14 Sep 2005 14:32:17 +0200, Jerzy Karczmarczuk wrote:
>> Here you are a recursive version linear in n; it
>> returns the two last Fibonacci numbers of the sequence

The minor problem is that for n = 0, there are no two last numbers.

>> def fibo(n):
>>       if n<2:
>>          return (n-1,n)
>>       else:
>>          (a,b)=fibo(n-1)
>>          return (b,a+b)
>
> Ah, I like this algorithm! I'll add it to my collection. Thank you.

The above is what I call the 'body recursive' form.  Others have other 
names.
Here is a version of the 'tail recursive' form (without negative input 
check).

def fibt(n):
  if n < 2: return n
  def _fib(i, a, b):
    if i < n:
      return _fib(i+1, b, a+b)
    return b
  return _fib(2, 1, 1)

The inner function does not have to be wrapped; for n >=2, the outer 
function simply passes on its final return.  However, the wrapping masks 
the accumulator parameters from the user and correctly sets their initial 
values.  It also handles the base cases more efficiently by checking for n 
< 2 just once instead of every inner loop.

Here is the direct iterative equivalent:

def fibi(n):
  if n < 2: return n        # same as before
  i, a, b = 2, 1, 1           # corresponds to initial _fib call
  while i < n:                # repeated ('recursive') if
    i, a, b = i+1, b, a+b  # corresponds to args of recursive _fib call
  return b                     # same as before

The transformation is mechanical and is done internally by some language 
interpreters.  (Although some might require the inner condition reversed 
and the returns switched.)

Terry J. Reedy