Fibonacci: How to think recursively

[Matteo Landi]

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

Regards,
Matteo

On Sun, Aug 29, 2010 at 2:23 AM, Ben Finney <ben+python at benfinney.id.au> wrote:
> Baba <raoulbia at gmail.com> 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
> --
> http://mail.python.org/mailman/listinfo/python-list
>



-- 
Matteo Landi
http://www.matteolandi.net/