Fibonacci: How to think recursively
mwilson at the-wire.com
Sun Aug 29 01:54:54 CEST 2010
> 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".
More information about the Python-list