Fibonacci: How to think recursively

[Albert van der Horst]

In article <i5c7ke$207$1 at speranza.aioe.org>, Mel  <mwilson at the-wire.com> 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 at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst