Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4185 > unrolled thread

Re: Fibonacci series recursion error

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#4185 — Re: Fibonacci series recursion error

On Sat, 30 Apr 2011 08:32:55 +0200, Peter Otten wrote:

> harrismh777 wrote:
> 
>> Ian Kelly wrote:
>>> since the fact is that if
>>> the function were properly coded, the call stack for fib(20) would
>>> never be more than 20 entries deep at any one time.
>>>
>>>
>> Not so much... and much more !....
>> 
>> 
>> ...  because each recursion level 'return' calls fib() twice, and each
>> of those calls fib() twice, and you get the point...
> 
> I don't understand what you are trying to say -- but it's wrong ;)


I don't know what M Harris thinks he is trying to say either, but the 
*naive* Fibonacci recursive algorithm is particularly badly performing 
and should be avoided. It's ironic that of the two classic algorithms 
used for teaching beginner programmers about recursion, neither is useful 
in practice.

Except for fib(0) and fib(1), each call to fib() results in multiple 
recursive calls. E.g. calling fib(4) results in the following sequence of 
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

Thus requiring nine function calls to calculate fib(4) and a maximum 
stack depth of four. As n increases, the number of calls increases at a 
rate significantly faster than the Fibonacci sequence itself, making it 
much worse than O(N**2) but not quite as bad as O(2**N):

    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 ...

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

Consequently, the naive recursive function is ridiculously slow and 
memory-hungry.

This seems to have give rise to a myth that recursion should be avoided. 
What needs to be avoided is *badly thought out* recursion. More sensible 
recursive forms performs much better. I leave them as an exercise for 
those who care, or an exercise in googling for those who care a little 
less *wink*



-- 
Steven

[toc] | [next] | [standalone]

#4425

"Steven D'Aprano" <steve+comp.lang.python@pearwood.info> wrote in message
news:4dbbb7b6$0$29991$c3e8da3$5496439d@news.astraweb.com...
> On Sat, 30 Apr 2011 08:32:55 +0200, Peter Otten wrote:
>
>> harrismh777 wrote:
>>
>>> Ian Kelly wrote:
>>>> since the fact is that if
>>>> the function were properly coded, the call stack for fib(20) would
>>>> never be more than 20 entries deep at any one time.
>>>>
>>>>
>>> Not so much... and much more !....
>>>
>>>
>>> ...  because each recursion level 'return' calls fib() twice, and each
>>> of those calls fib() twice, and you get the point...
>>
>> I don't understand what you are trying to say -- but it's wrong ;)
>
>
> I don't know what M Harris thinks he is trying to say either, but the
> *naive* Fibonacci recursive algorithm is particularly badly performing
> and should be avoided. It's ironic that of the two classic algorithms
> used for teaching beginner programmers about recursion, neither is useful
> in practice.

Yes, it generates lots of calls.

About 22000 for fib(20), and 330 million for fib(40).

That's why it's popular for benchmarks that measure performance of function
calls. Using an iterative algorithm wouldn't work quite so well...

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#4433

On 5/1/2011 7:16 PM, BartC wrote:

> Yes, it generates lots of calls.
>
> About 22000 for fib(20), and 330 million for fib(40).

Using the standard double recursion implementation of fib, ncf(n) 
(number of calls to fib() for fib(n)) requires ncf(n-2) + ncf(n+1) + 1 
calls. The +1 is for the call to fib(n) itself). So it grows a bit 
faster than fib(n).

Fib(n) is actually calculated as the sum of fib(n) 1s: 1+1+1....+1 
fib(n) times as 1 is the only non-0 base case and there is nothing else 
added or multiplied in non-base cases. To put it another way, there are 
fib(n) leaf nodes labeled 1 in the unbalanced tree generated by the 
recursion.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#4458

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 :-)

[toc] | [prev] | [next] | [standalone]

#4461

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

[toc] | [prev] | [next] | [standalone]

#4467

On 02 May 2011 08:56:57 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  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.

Well, Fibonacci isn't one unique sequence.  Any sequence satisfying
f(n) = f(n-1) + f(n-2) is /a/ Fibonacci sequence.  Regardless of 
starting values.  At least according to some authors.

Ian Andersen (A First Course in Combinatorial Mathematics) prefer 
the sequence 1,2,3,5 ...

Cormen, Leiserson, Rivest (Introduction to Algorithms) prefer
0,1,1,2, ... (although they also start the indexing at 0).

Penguin, Dict. of Mathematics prefer 1,1,2,3,5 but they also
suggest 0,1,1,2,3, ...

In short, don't assume that a person talking about Fibonacci
numbers assume the same base cases as you do.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4472

On May 2, 2:53 pm, Hans Georg Schaathun <h...@schaathun.net> wrote:
> On 02 May 2011 08:56:57 GMT, Steven D'Aprano  <steve+comp.lang.pyt...@pearwood.info> wrote:
>
> :  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.
>
> Well, Fibonacci isn't one unique sequence.  Any sequence satisfying
> f(n) = f(n-1) + f(n-2) is /a/ Fibonacci sequence.  Regardless of
> starting values.  At least according to some authors.

And they all will, when expressed in closed form, be of the form
f(n) = phi^n + something of a smaller order
where phi = (1 + sqrt(5))/2

Since phi > 1 they are exponential, ignoring lower order terms.

[toc] | [prev] | [next] | [standalone]

#4483

On Mon, 02 May 2011 10:53:52 +0100, Hans Georg Schaathun wrote:

> On 02 May 2011 08:56:57 GMT, Steven D'Aprano
>   <steve+comp.lang.python@pearwood.info> wrote:
> :  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.
> 
> Well, Fibonacci isn't one unique sequence.  Any sequence satisfying f(n)
> = f(n-1) + f(n-2) is /a/ Fibonacci sequence.  Regardless of starting
> values.  At least according to some authors.

According to the references I have, there is one and only one Fibonacci 
sequence, the usual one invented by Fibonacci to talk about rabbits. 
(Actually, we should talk about Fibonacci *numbers*, rather than 
sequence.)

Wolfram Mathworld is typical, defining *the* Fibonacci numbers as those 
with starting conditions f(1)=1, f(2)=1 (or f(0)=0 if you prefer).

http://mathworld.wolfram.com/FibonacciNumber.html

The Collins Dictionary of Mathematics agrees with Mathworld.

The Lucas numbers (related to, but not the same as, the Lucas sequence) 
obey the same recurrence as the Fibonacci numbers, but with a different 
set of starting values. So there is certainly precedent in the 
mathematical literature for giving different names to the same recurrence 
with different starting values.

In any case, whatever you call them, what I call R(n) is not one, as the 
recurrence is different:

R(n) = R(n-1) + R(n-2) + 1


> Penguin, Dict. of Mathematics prefer 1,1,2,3,5 but they also suggest
> 0,1,1,2,3, ...

This depends on whether you start counting from n=0 or n=1.

Even the sequence you quote, from Anderson: 

1,2,3,5...

is just the usual Fibonacci numbers starting at n=2 instead of 1 or 0. 
(No matter how confusing something is, there's always at least one person 
who will try to make it *more* confusing.)


> In short, don't assume that a person talking about Fibonacci numbers
> assume the same base cases as you do.

As far as I'm concerned, there are only two definitions of Fibonacci 
numbers that have widespread agreement in the mathematical community:

0,1,1,2,3 ... (starting from n=0)
1,1,2,3,5 ... (starting from n=1)

Any other definition is rather, shall we say, idiosyncratic.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4500

On May 2, 5:24 pm, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:

> As far as I'm concerned, there are only two definitions of Fibonacci
> numbers that have widespread agreement in the mathematical community:
>
> 0,1,1,2,3 ... (starting from n=0)
> 1,1,2,3,5 ... (starting from n=1)
>
> Any other definition is rather, shall we say, idiosyncratic.

And a concrete reason for preferring the above definition (in either
form) is that divisibility properties of the sequence are much neater
with this choice:

    gcd(F_m, F_n) = F_{gcd(m, n)}

--
Mark

[toc] | [prev] | [next] | [standalone]

#4600

On Mon, May 2, 2011 at 6:56 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> (The fact that most of those start with P is almost certainly a
> coincidence.)
>

There's definitely something attractive about that letter. Lots of
programming languages' names start with P. I smell a conspiracy. The
word "programming" has been secretly attracting related words to its
corner of the alphabet... and the government's *covering it up* and
pretending there's nothing happening!

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4686

Chris Angelico wrote:

> There's definitely something attractive about that letter. Lots of
> programming languages' names start with P.

Including one I invented some years ago, that (in the spirit
of C and its derivatives) was called simply "P".

(I was playing around with Sun's NeWS window server, which
was programmed in Postscript, and I got fed up with Forth-like
syntax, so I wrote a translator that took an infix language and
generated Postscript from it.)

-- 
Greg

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web