# Fibonacci: How to think recursively

Discussion in 'Python' started by Baba, Aug 29, 2010.

1. ### BabaGuest

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

OR

def fibonacci(n):
# base case:
fibonacci(n+2) - fibonacci(n+1) - n = 0
>> this too would create overlapping recursions

Thanks
Baba

Baba, Aug 29, 2010

2. ### MelGuest

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.

Mel, Aug 29, 2010

3. ### Matteo LandiGuest

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 <> wrote:
> Baba <> 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/

Matteo Landi, Aug 29, 2010
4. ### Steven D'ApranoGuest

On Sat, 28 Aug 2010 16:12:36 -0700, 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:

ideas. Let's look at factorial first.

fact(n) = n*(n-1)*(n-2)*(n-3)*...*2*1

Working upwards:

fact(0) = 1 # this is by definition.
fact(1) = 1 # also by definition.
fact(2) = 2*1 = 2*fact(1)
fact(3) = 3*2*1 = 3*fact(2)
....
fact(n) = n*fact(n-1)

So now you have the base case:
if n is 1 or smaller, fact(n) returns 1

and the recursive case:
otherwise fact(n) returns n*fact(n-1)

Now write that as a Python function, and test it to see that it is
correct. Come back once you've got it working satisfactorily.

Now, can you apply the same reasoning to the Fibonacci problem?

What is your base case? You need some way to halt the recursion,
something that *doesn't* make a recursive call.

def fib(n):
if SOME_CONDITION:
return SOME_VALUE
else:
return SOME_RECURSION

is the most basic form you can have. Notice that you must *return*
something. That's basic Python syntax -- if you don't call return, the
function will return the special None object, which is not what you want.

More generally, you could have multiple base cases and multiple recursive
cases, not necessarily one of each. But there must be at least one non-
recursive expression that gets returned, or the recursion can never
terminate.

> 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

Mathematically, there is nothing wrong with overlapping recursion. It
will work, and Python can handle it easily.

But in practical terms, it can lead to great inefficiency. In this
example, it should be avoided because it is slow. Very slow. To calculate
the nth Fibonacci number using naive recursion requires *many* calls:

fib(4) # first call
=> fib(3) + fib(2) # three calls
=> fib(2) + fib(1) + fib(1) + fib(0) # seven calls
=> fib(1) + fib(0) + 1 + 1 + 0 # nine calls
=> 1 + 0 + 1 + 1 + 0 = 3

So to get fib(4) = 3 requires nine calls to fib().

This growth function doesn't have a name (as far as I know), but it grows
much faster than fib() itself:

n = 0 1 2 3 4 5 6 ... 35 ...
fib(n) = 0 1 1 2 3 5 8 ... 9227465 ...
calls = 1 1 3 5 9 15 25 ... 29860703 ...

As you can see, the number of calls is also calculable by a recursive
expression R:

R(0) = R(1) = 1
R(n) = R(n-1) + R(n-2) + 1

This is very similar to the Fibonacci recursion, only it grows more
quickly. But I digress...

You can make the recursive version more efficient if you give it a
memory. In the call to fib(5), for example, it ends up calling fib(4)
once, fib(3) twice, fib(2) three times, fib(1) four times, and fib(0)
twice. If it could remember each value once it saw it, it could
potentially save nine calls (out of fifteen). That's a less inefficient
use of recursion. Think about ways to give it a short-term memory.

You can make it even more efficient by giving fib() a long-term cache, so
that each call to fib(5) requires one cache lookup rather than six (or
fifteen) recursive calls. Other than the first time, obviously. This is
called memoisation, but again I digress.

There are other techniques, but this will do to get started.

--
Steven

Steven D'Aprano, Aug 29, 2010
5. ### Mark TolonenGuest

"Steven D'Aprano" <> wrote in message
news:4c79c510\$0\$28655\$...
> On Sat, 28 Aug 2010 16:12:36 -0700, Baba wrote:

> There are other techniques, but this will do to get started.

Once you realize recursion for Fibonacci numbers is still fairly slow, look
up generator functions :^)

-Mark

Mark Tolonen, Aug 29, 2010
6. ### Chris RebertGuest

On Sat, Aug 28, 2010 at 7:25 PM, Steven D'Aprano
<> wrote:
> On Sat, 28 Aug 2010 16:12:36 -0700, Baba wrote:
>> Level: beginner
>>
>> I would like to know how to approach the following Fibonacci problem:

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

>
> Mathematically, there is nothing wrong with overlapping recursion. It
> will work, and Python can handle it easily.
>
> But in practical terms, it can lead to great inefficiency. In this
> example, it should be avoided because it is slow. Very slow. To calculate
> the nth Fibonacci number using naive recursion requires *many* calls:
>
> Â  Â fib(4) Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â # first call
> Â  Â => fib(3) + fib(2) Â  Â  Â  Â  Â  Â  Â  Â  Â  Â # three calls
> Â  Â => fib(2) + fib(1) + fib(1) + fib(0) Â # seven calls
> Â  Â => fib(1) + fib(0) + 1 + 1 + 0 Â  Â  Â  Â # nine calls
> Â  Â => 1 + 0 + 1 + 1 + 0 = 3
>
> So to get fib(4) = 3 requires nine calls to fib().
>
> This growth function doesn't have a name (as far as I know),

It's A001595 in OEIS; http://www.research.att.com/~njas/sequences/A001595
"Sometimes called 'Leonardo numbers'"
Also apparently "2-ranks of difference sets constructed from Segre hyperovals."

> but it grows
> much faster than fib() itself:
>
> n Â  Â  Â = 0 Â  1 Â  2 Â  3 Â  4 Â  5 Â  6 Â  ... 35 Â  Â  Â  ...
> fib(n) = 0 Â  1 Â  1 Â  2 Â  3 Â  5 Â  8 Â  ... 9227465 Â ...
> calls Â = 1 Â  1 Â  3 Â  5 Â  9 Â  15 Â 25 Â ... 29860703 ...
>
> As you can see, the number of calls is also calculable by a recursive
> expression R:
>
> R(0) = R(1) = 1
> R(n) = R(n-1) + R(n-2) + 1
>
> This is very similar to the Fibonacci recursion, only it grows more
> quickly. But I digress...

Other formulations courtesy OEIS:

R(n) = sum(fib(i) for i in range(1, n+1)) - fib(n-1)

R(n) = 2*fib(n+1) - 1

Cheers,
Chris
--
http://blog.rebertia.com

Chris Rebert, Aug 29, 2010
7. ### News123Guest

On 08/29/2010 01:12 AM, 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

>
> OR
>
> def fibonacci(n):
> # base case:
> fibonacci(n+2) - fibonacci(n+1) - n = 0
>>> this too would create overlapping recursions

>

Hi Baba,

Let's take another example: factorials:
Trivial, but you 'just have to apply the same techniques FIbonacci

n! = 1 * 2 * 3 . . . * n

Very first thing is to always find a trivial case, or the terminal
condition.
Tjis is, when you reduced the problem to the most trivial case(s), for
which you don't need anymore recursion

for factorials this would be
0! = 1
for Fibonacci you might have multiple trivial cases

and the recursive definition of factorial is\
n! = (n - 1) * n

so the code for factorial looks something like:

def factorial(n):
if n == 0:
# treat the trivial case / cases for which ou know the answer
return 1
else:
# reduce the problem by the recursive definition
return factorial(n-1)*n

Hope this helps.

News123, Aug 29, 2010
8. ### BabaGuest

On Aug 29, 3:25 am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:

> Mathematically, there is nothing wrong with overlapping recursion. It
> will work, and Python can handle it easily.

Based on the advice by Steven and Mel i tried my initial 'guess' and
it does seem to work fine. When looking at it using pencil and paper i
thought "well, each recursive call will call 2 new ones and if n is
large i will have a huge overlap, so it probably is the wrong
approach". However it turns out to be fine in principle. It can be
handled, as Steven pointed out.

> But in practical terms, it can lead to great inefficiency. In this
> example, it should be avoided because it is slow. Very slow. To calculate
> the nth Fibonacci number using naive recursion requires *many* calls:
>
> You can make it even more efficient by giving fib() a long-term cache, so
> that each call to fib(5) requires one cache lookup rather than six (or
> fifteen) recursive calls. Other than the first time, obviously. This is
> called memoisation, but again I digress.
>

I looked memoisation up and decided that for now i will not go near
it. First i will try to build up some bacic skills but thank you very
much for the hint. Memoisation will certainly be on the list of future
exercises.

However, the idea that memoisation is needed to make the computation
more efficient confirms my initial feeling that a 'simple' recursive
approach is somewhat not ideal.

So here's my code. It does still cause me one headache. If i use
f(0)=0
and f(1)=1 as base cases the result will be 144. I was expecting the
result to be the next value in the series (233)...
If i use f(1)=1 and f(2)=2 as base cases them i get my expected
result. I assume this has to do with our understanding/defining the
start of the Fibonacci series?

def r_fib(n):
if n == 1: return 1
elif n == 2: return 2
else: return r_fib(n-2) + r_fib(n-1)

print r_fib(12)

Thanks
Baba

Baba, Aug 29, 2010
9. ### Alain KetterlinGuest

Baba <> writes:

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

fib(n) = fib(n-1) + fib(n-2), so you need the two previous values to
compute the next one (that's the main difference between fibonacci and
factorial). So here is a hint: instead of computing only fib(n), compute
a pair (fib(n),fib(n-1)). It now becomes a problem very similar to
factorial: for instance, what's (fib(7),fib(6)) if you have the values
of (fib(6),fib(5))? Now write a recursive function fib2(n) that returns
the last two values. And a simple wrapper fib(n) that calls fib2(n) and
returns the first element of the pair.

-- Alain.

Alain Ketterlin, Aug 29, 2010
10. ### News123Guest

Hi Baba,

> So here's my code. It does still cause me one headache. If i use
> f(0)=0
> and f(1)=1 as base cases the result will be 144. I was expecting the
> result to be the next value in the series (233)...
> If i use f(1)=1 and f(2)=2 as base cases them i get my expected
> result. I assume this has to do with our understanding/defining the
> start of the Fibonacci series?
>
>
> def r_fib(n):
> if n == 1: return 1
> elif n == 2: return 2
> else: return r_fib(n-2) + r_fib(n-1)
>
> print r_fib(12)
>

Let's calculate the first 12 Fobonacci numbers first manually:

0: 0 # as of its definition
1: 1 @ as of its definition
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3
5: 2 + 3 = 5
6: 3 + 5 = 8
7: 5 + 8 = 13
8: 8 + 13 = 21
9: 13 + 21 = 34
10: 21 + 34 = 55
11: 34 + 55 = 89
12: 55 + 89 = 144

So if you use f(0) = 0 and f(1) = 1 you seem to get the coorec result,
right?

Now the question is why you get the wrong result with your code:

def r_fib(n):
if n == 1: return 1
elif n == 2: return 2
else: return r_fib(n-2) + r_fib(n-1)

You wrote, that it is 2, but it should be 1

News123, Aug 29, 2010
11. ### BabaGuest

Thanks to All for your kind help!

Baba

Baba, Aug 29, 2010
12. ### Steven D'ApranoGuest

On Sun, 29 Aug 2010 06:43:40 -0700, Baba wrote:

> So here's my code. It does still cause me one headache. If i use f(0)=0
> and f(1)=1 as base cases the result will be 144. I was expecting the
> result to be the next value in the series (233)...

That's because you're not generating the Fibonacci series, but a similar
unnamed(?) series with the same recurrence but different starting
conditions. The Fibinacci series starts with f(0)=1, f(1)=1.

> If i use f(1)=1 and
> f(2)=2 as base cases them i get my expected result.

Which implies that f(0) must be 1, not 0.

--
Steven

Steven D'Aprano, Aug 30, 2010
13. ### Albert van der HorstGuest

In article <i5c7ke\$207\$>, Mel <> wrote:
>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".

[Didn't you mean: I don't understand what you mean by overlapping
recursions? You're right about the base case, so clearly the OP
uses some confusing terminology.]

I see a problem with overlapping recursions. Unless automatic memoizing
is one, they are unduely inefficient, as each call splits into two
calls.

If one insists on recursion (untested code, just for the idea.).

def fib2( n ):
' return #rabbits last year, #rabbits before last '
if n ==1 :
return (1,1)
else
penult, ult = fib2( n-1 )
return ( ult, ult+penult)

def fub( n ):
return fib2(n)[1]

Try fib and fub for largish numbers (>1000) and you'll feel the
problem.

>
> Mel.
>

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Albert van der Horst, Sep 1, 2010
14. ### Neil CeruttiGuest

On 2010-09-01, Albert van der Horst <4all.nl> wrote:
> [Didn't you mean: I don't understand what you mean by
> overlapping recursions? You're right about the base case, so
> clearly the OP uses some confusing terminology.]
>
> I see a problem with overlapping recursions. Unless automatic
> memoizing is one, they are unduely inefficient, as each call
> splits into two calls.
>
> If one insists on recursion (untested code, just for the idea.).
>
> def fib2( n ):
> ' return #rabbits last year, #rabbits before last '
> if n ==1 :
> return (1,1)
> else
> penult, ult = fib2( n-1 )
> return ( ult, ult+penult)
>
> def fub( n ):
> return fib2(n)[1]
>
> Try fib and fub for largish numbers (>1000) and you'll feel the
> problem.

There are standard tricks for converting a recursive iteration
into a tail-recursive one. It's usually done by adding the
necessary parameters, e.g.:

def fibr(n):
def fib_helper(fibminus2, fibminus1, i, n):
if i == n:
return fibminus2 + fibminus1
else:
return fib_helper(fibminus1, fibminus1 + fibminus2, i+1, n)
if n < 2:
return 1
else:
return fib_helper(1, 1, 2, n)

Once you've got a tail-recursive solution, you can usually
convert it to loop iteration for languages like Python that favor
them. The need for a temporary messed me up.

def fibi(n):
if n < 2:
return 1
else:
fibminus2 = 1
fibminus1 = 1
i = 2
while i < n:
fibminus2, fibminus1 = fibminus1, fibminus2 + fibminus1
i += 1
return fibminus2 + fibminus1

It's interesting that the loop iterative solution is, for me,
harder to think up without doing the tail-recursive one first.

--
Neil Cerutti

Neil Cerutti, Sep 1, 2010
15. ### MikeGuest

The most straightforward method would be to apply the formula
directly.
Loop on j computing Fj along the way
if n<=1 : return n

Fold=0
Fnew=1
for j in range(2,n) :
Fold, Fnew = Fnew, Fold+Fnew
return Fnew

Even simpler:
return round(((1+sqrt(5.))/2)**n/sqrt(5.))

Mike, Sep 1, 2010