On Mon, 02 May 2011 01:27:39 -0700, rusi wrote: > 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
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 -- http://mail.python.org/mailman/listinfo/python-list
