Fibonacci: How to think recursively

[Alain Ketterlin]

Baba <raoulbia at gmail.com> writes:

> Level: beginner
>
> I would like to know how to approach the following Fibonacci problem:
> How may rabbits do i have after n months?
>
> I'm not looking for the code as i could Google that very easily. I'm
> looking for a hint to put me on the right track to solve this myself
> without looking it up.

fib(n) = fib(n-1) + fib(n-2), so you need the two previous values to
compute the next one (that's the main difference between fibonacci and
factorial). So here is a hint: instead of computing only fib(n), compute
a pair (fib(n),fib(n-1)). It now becomes a problem very similar to
factorial: for instance, what's (fib(7),fib(6)) if you have the values
of (fib(6),fib(5))? Now write a recursive function fib2(n) that returns
the last two values. And a simple wrapper fib(n) that calls fib2(n) and
returns the first element of the pair.

-- Alain.