Fibonacci series recursion error

[rusi]

On Apr 30, 12:18 pm, Steven D'Aprano <steve
+comp.lang.pyt... at 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 :-)