"Steven D'Aprano" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> 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
--
http://mail.python.org/mailman/listinfo/python-list
