# Fibonacci: How to think recursively

Ben Finney ben+python at benfinney.id.au
Sun Aug 29 02:23:52 CEST 2010

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

```