Fibonacci: How to think recursively

[Neil Cerutti]

On 2010-09-01, Albert van der Horst <albert at spenarnc.xs4all.nl> wrote:
> [Didn't you mean: I don't understand what you mean by
> overlapping recursions?  You're right about the base case, so
> clearly the OP uses some confusing terminology.]
>
> I see a problem with overlapping recursions. Unless automatic
> memoizing is one, they are unduely inefficient, as each call
> splits into two calls.
>
> If one insists on recursion (untested code, just for the idea.).
>
> def fib2( n ):
>      ' return #rabbits last year, #rabbits before last '
>      if n ==1 :
>          return (1,1)
>      else
>          penult, ult = fib2( n-1 )
>          return ( ult, ult+penult)
>
> def fub( n ):
>    return fib2(n)[1]
>
> Try fib and fub for largish numbers (>1000) and you'll feel the
> problem.

There are standard tricks for converting a recursive iteration
into a tail-recursive one. It's usually done by adding the
necessary parameters, e.g.:

def fibr(n):
    def fib_helper(fibminus2, fibminus1, i, n):
        if i == n:
            return fibminus2 + fibminus1
        else:
            return fib_helper(fibminus1, fibminus1 + fibminus2, i+1, n)
    if n < 2:
        return 1
    else:
        return fib_helper(1, 1, 2, n)

Once you've got a tail-recursive solution, you can usually
convert it to loop iteration for languages like Python that favor
them. The need for a temporary messed me up.

def fibi(n):
    if n < 2:
        return 1
    else:
        fibminus2 = 1
        fibminus1 = 1
        i = 2
        while i < n: 
            fibminus2, fibminus1 = fibminus1, fibminus2 + fibminus1
            i += 1
        return fibminus2 + fibminus1

It's interesting that the loop iterative solution is, for me,
harder to think up without doing the tail-recursive one first.

-- 
Neil Cerutti