Re: Fibonacci series recursion error

From	rusi <rustompmody@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: Fibonacci series recursion error
Date	2011-05-02 01:27 -0700
Organization	http://groups.google.com
Message-ID	<b2ead254-e3ca-4bd1-a879-eba2e44af23c@q12g2000prb.googlegroups.com> (permalink)
References	(1 earlier) <BANLkTimfNQhdE1ZJwP_HN64WwERtUOtBvw@mail.gmail.com> <mailman.1011.1304141265.9059.python-list@python.org> <vcNup.5316$Du7.1273@newsfe04.iad> <ipgaej$ma5$1@solani.org> <4dbbb7b6$0$29991$c3e8da3$5496439d@news.astraweb.com>

Show all headers | View raw

On Apr 30, 12:18 pm, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:

> The number of calls is given by a recursive function with a similar form
> as that of Fibonacci. As far as I know, it doesn't have a standard name,
> but I'll call it R(n):
>
> R(n) = R(n-1) + R(n-2) + 1, where R(0) = R(1) = 1

Changing your definition slightly to the following:

def r(n):
    if n==0 or n==1: return 0
    else: return r(n-1) + r(n-2) + 1


This r counts the number of times the '+' is done in the original
(naive) fib.

We see it is the same as fib (off by 1)

>>> [fib(n) for n in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> [r(n) for n in range(10)]
[0, 0, 1, 2, 4, 7, 12, 20, 33, 54]
>>>

So it does not need a new name :-)

Thread

Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-04-30 07:18 +0000
  Re: Fibonacci series recursion error "BartC" <bc@freeuk.com> - 2011-05-02 00:16 +0100
    Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-01 22:30 -0400
  Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 01:27 -0700
    Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 08:56 +0000
      Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 10:53 +0100
        Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 03:40 -0700
        Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 16:24 +0000
          Re: Fibonacci series recursion error Mark Dickinson <dickinsm@gmail.com> - 2011-05-02 14:18 -0700
      Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 19:03 +1000
        Re: Fibonacci series recursion error Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-05 14:35 +1200

csiph-web