Fibonacci: How to think recursively

[Steven D'Aprano]

On Sat, 28 Aug 2010 16:12:36 -0700, Baba wrote:

> 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.
> 
> my brainstorming so far brought me to a stand still as i can't seem to
> imagine a recursive way to code this:


Perhaps you need to start with a simpler case to get your head around the 
ideas. Let's look at factorial first.

fact(n) = n*(n-1)*(n-2)*(n-3)*...*2*1

Working upwards:

fact(0) = 1  # this is by definition.
fact(1) = 1  # also by definition.
fact(2) = 2*1 = 2*fact(1)
fact(3) = 3*2*1 = 3*fact(2)
...
fact(n) = n*fact(n-1)

So now you have the base case:
    if n is 1 or smaller, fact(n) returns 1

and the recursive case:
    otherwise fact(n) returns n*fact(n-1)

Now write that as a Python function, and test it to see that it is 
correct. Come back once you've got it working satisfactorily.



Now, can you apply the same reasoning to the Fibonacci problem?

What is your base case? You need some way to halt the recursion, 
something that *doesn't* make a recursive call.

def fib(n):
    if SOME_CONDITION:
        return SOME_VALUE
    else:
        return SOME_RECURSION

is the most basic form you can have. Notice that you must *return* 
something. That's basic Python syntax -- if you don't call return, the 
function will return the special None object, which is not what you want.

More generally, you could have multiple base cases and multiple recursive 
cases, not necessarily one of each. But there must be at least one non-
recursive expression that gets returned, or the recursion can never 
terminate.


> my attempted rough code:
> 
> def fibonacci(n):
>     # base case:
>         result = fibonacci (n-1) + fibonacci (n-2)
>>> this will end up in a mess as it will create overlapping recursions

Mathematically, there is nothing wrong with overlapping recursion. It 
will work, and Python can handle it easily.

But in practical terms, it can lead to great inefficiency. In this 
example, it should be avoided because it is slow. Very slow. To calculate 
the nth Fibonacci number using naive recursion requires *many* calls:

    fib(4)                                # first call
    => fib(3) + fib(2)                    # three calls
    => fib(2) + fib(1) + fib(1) + fib(0)  # seven calls
    => fib(1) + fib(0) + 1 + 1 + 0        # nine calls
    => 1 + 0 + 1 + 1 + 0 = 3

So to get fib(4) = 3 requires nine calls to fib().

This growth function doesn't have a name (as far as I know), but it grows 
much faster than fib() itself:

n      = 0   1   2   3   4   5   6   ... 35       ...
fib(n) = 0   1   1   2   3   5   8   ... 9227465  ...
calls  = 1   1   3   5   9   15  25  ... 29860703 ...

As you can see, the number of calls is also calculable by a recursive 
expression R:

R(0) = R(1) = 1
R(n) = R(n-1) + R(n-2) + 1

This is very similar to the Fibonacci recursion, only it grows more 
quickly. But I digress...


You can make the recursive version more efficient if you give it a 
memory. In the call to fib(5), for example, it ends up calling fib(4) 
once, fib(3) twice, fib(2) three times, fib(1) four times, and fib(0) 
twice. If it could remember each value once it saw it, it could 
potentially save nine calls (out of fifteen). That's a less inefficient 
use of recursion. Think about ways to give it a short-term memory.

You can make it even more efficient by giving fib() a long-term cache, so 
that each call to fib(5) requires one cache lookup rather than six (or 
fifteen) recursive calls. Other than the first time, obviously. This is 
called memoisation, but again I digress.


There are other techniques, but this will do to get started.




-- 
Steven