Fibonacci series recursion error

[Steven D'Aprano]

On Mon, 02 May 2011 01:27:39 -0700, rusi wrote:

> 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

Except that's not the same as my "R(n)". The base cases should be 1, not 
0. That makes rather a big difference to the value: by n = 35, you have 

R(35) = 29860703 
fib(35) = 9227465

or nearly 2.25 times greater. And the difference just keeps getting 
bigger...


> We see it is the same as fib (off by 1)
[...]
> So it does not need a new name :-)

I see your smiley, but there are a number of similar series as Fibonacci, 
with the same recurrence but different starting values, or similar but 
slightly different recurrences. E.g. Lucas, primefree, Pell, Padovan and 
Perrin numbers.

(The fact that most of those start with P is almost certainly a 
coincidence.)



-- 
Steven