Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Fibonacci: How to think recursively

Reply
Thread Tools

Fibonacci: How to think recursively

 
 
Baba
Guest
Posts: n/a
 
      08-28-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


OR

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



How to go about this?

Thanks
Baba

 
Reply With Quote
 
 
 
 
Mel
Guest
Posts: n/a
 
      08-28-2010
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.

 
Reply With Quote
 
 
 
 
Matteo Landi
Guest
Posts: n/a
 
      08-29-2010
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 <(E-Mail Removed)> wrote:
> Baba <(E-Mail Removed)> 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/
 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      08-29-2010
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:



Perhaps you need to start with a simpler case to get your head around the
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
 
Reply With Quote
 
Mark Tolonen
Guest
Posts: n/a
 
      08-29-2010

"Steven D'Aprano" <(E-Mail Removed)> wrote in message
news:4c79c510$0$28655$(E-Mail Removed)...
> 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


 
Reply With Quote
 
Chris Rebert
Guest
Posts: n/a
 
      08-29-2010
On Sat, Aug 28, 2010 at 7:25 PM, Steven D'Aprano
<(E-Mail Removed)> 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
 
Reply With Quote
 
News123
Guest
Posts: n/a
 
      08-29-2010
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.





 
Reply With Quote
 
Baba
Guest
Posts: n/a
 
      08-29-2010
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
 
Reply With Quote
 
Alain Ketterlin
Guest
Posts: n/a
 
      08-29-2010
Baba <(E-Mail Removed)> 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.
 
Reply With Quote
 
News123
Guest
Posts: n/a
 
      08-29-2010
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)


The answer is very simple your result n=2 is wrong.
You wrote, that it is 2, but it should be 1




 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
I think I will get this and I think I will get that =?iso-8859-1?Q?mark=5Fdigital=A9?= Digital Photography 19 03-18-2006 01:42 AM
Need help: Is Quick-Union-Find the right solution to this problem (Now I don't think so and I think that topological sorting should be the way to go...?) ? aredo3604gif@yahoo.com C Programming 0 04-12-2005 05:06 PM
Think your Wireless Network is Secure? Think Again. Careers Computer Security 7 01-31-2004 07:04 AM
Think Off Brand Inks Are Just as Good in your Inkjet Printer - Think Again! John Horner Digital Photography 5 11-09-2003 09:38 PM



Advertisments