Fibonacci: How to think recursively

[Mel]

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

I don't think this is the base case.  The base case would be one or more 
values of `n` that you already know the fibonacci number for.  Your 
recursive function can just test for those and return the right answer right 
away.  The the expression you've coded contains a good way to handle the 
non-base cases.  There's no such problem as "overlapping recursions".

	Mel.