Fibonacci: How to think recursively

Matteo Landi landimatte at
Sun Aug 29 02:33:30 CEST 2010

I suggest you to memoize results in order to prevent overlapping recursion.


On Sun, Aug 29, 2010 at 2:23 AM, Ben Finney <ben+python at> wrote:
> Baba <raoulbia at> writes:
>> 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
> It also never returns anything (which, in Python, means it returns the
> None object).
> Worse, it will endlessly recurse; every time it's called it will call
> itself (twice).
> Perhaps a way to approach the problem is: How will your function know
> when *not* to call itself? What will it do instead? Try writing that
> case first, and then write the rest of it on that basis.
> --
>  \         “Science is a way of trying not to fool yourself. The first |
>  `\     principle is that you must not fool yourself, and you are the |
> _o__)               easiest person to fool.” —Richard P. Feynman, 1964 |
> Ben Finney
> --

Matteo Landi

More information about the Python-list mailing list