Fibonacci: How to think recursively

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

  1. Baba

    Baba Guest

    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
     
    Baba, Aug 29, 2010
    #1
    1. Advertising

  2. Baba

    Mel Guest

    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
    #2
    1. Advertising

  3. Baba

    Matteo Landi Guest

    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
    #3
  4. 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
     
    Steven D'Aprano, Aug 29, 2010
    #4
  5. Baba

    Mark Tolonen Guest

    "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
    #5
  6. Baba

    Chris Rebert Guest

    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
    #6
  7. Baba

    News123 Guest

    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
    #7
  8. Baba

    Baba Guest

    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
    #8
  9. 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
    #9
  10. Baba

    News123 Guest

    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
     
    News123, Aug 29, 2010
    #10
  11. Baba

    Baba Guest

    Thanks to All for your kind help!

    Baba
     
    Baba, Aug 29, 2010
    #11
  12. 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
    #12
  13. 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
    #13
  14. Baba

    Neil Cerutti Guest

    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
    #14
  15. Baba

    Mike Guest

    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
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brett Trost

    Fibonacci problem

    Brett Trost, Jan 22, 2004, in forum: Perl
    Replies:
    2
    Views:
    1,042
  2. fighterman19
    Replies:
    11
    Views:
    881
    Karl Heinz Buchegger
    Sep 8, 2003
  3. Replies:
    0
    Views:
    642
  4. Replies:
    1
    Views:
    910
    Jack Klein
    Apr 13, 2005
  5. David Mark
    Replies:
    17
    Views:
    265
    David Mark
    Mar 23, 2010
Loading...

Share This Page