Fibonacci series recursion error

[rusi]

On Apr 30, 11:14 am, Peter Otten <__pete... at web.de> wrote:

> For the record, the one true way to implement the Fibonacci series in Python
> is
>
> >>> def fib():
>
> ...     a = b = 1
> ...     while True:
> ...             yield a
> ...             a, b = b, a+b # look ma, no temporary variable

Not any claim to 'the one true pythonic way' but fib can be written in
a clean recursive way with linear space-time behavior asz follows:

Dijkstra explained that fib is an 2nd order recurrence
-- fib(n) defined in terms of fib (n-1) and fib(n-2)
whereas programming loops and recursion are 1st order -- state at
iteration n defines state at iteration n+1.

Converting the 2nd order fib relation to a 1st order one trivially
gives a linear program.
The key insight from Dijkstra is that all we need to do is to move
from a recursive function returning fibonacci nos to one returning
pairs of adjacent ones.

def fibpair(n):
    # returns (fib(n), fib(n+1))
    if n==0:
        return (1,1)
    else:
        (a,b) = fibpair(n-1)
        return (b, a+b)

After that fib is just this:

def fib(n):
    a,b = fibpair(n)
    return a;