# Fibonacci: How to think recursively

Neil Cerutti neilc at norwich.edu
Wed Sep 1 16:19:07 CEST 2010

```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

```