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

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

Re: fibonacci series what Iam is missing ?

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 what Iam is missing ? Chris Angelico <rosuav@gmail.com> - 2015-03-24 03:16 +1100
    Re: fibonacci series what Iam is missing ? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-24 11:19 +1100
      Re: fibonacci series what Iam is missing ? Dave Angel <davea@davea.name> - 2015-03-23 20:42 -0400
      Re: fibonacci series what Iam is missing ? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-24 11:56 +1100
      Re: fibonacci series what Iam is missing ? Chris Angelico <rosuav@gmail.com> - 2015-03-24 11:59 +1100
        Re: fibonacci series what Iam is missing ? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-24 12:52 +1100
          Re: fibonacci series what Iam is missing ? Rustom Mody <rustompmody@gmail.com> - 2015-03-23 19:23 -0700
          Re: fibonacci series what Iam is missing ? Chris Angelico <rosuav@gmail.com> - 2015-03-24 14:03 +1100
            Re: fibonacci series what Iam is missing ? Rustom Mody <rustompmody@gmail.com> - 2015-03-23 20:30 -0700
            Re: fibonacci series what Iam is missing ? Rustom Mody <rustompmody@gmail.com> - 2015-03-23 21:13 -0700

#87834 — Re: fibonacci series what Iam is missing ?

On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal <ganesh1pal@gmail.com> wrote:
> Hello team ,
>
>
> [root@localhost Python]# cat  fibonacci-Sequence-3.py
>
> ## Example 2: Using recursion
> def fib(n):
>     if n == 0:
>         return 0
>     elif n == 1:
>         return 1
>     else:
>         return fib(n-1) + fib(n-2)
> print fib(5)
>
> # python  fibonacci-Sequence-3.py
> 5
>
> what Iam I missing in the program , I was expecting 0,1,1,2,3 ?

What you're doing is printing out the fifth Fibonacci number. So there
are three things to note:

1) To display the entire sequence, you will need some sort of loop.
2) Your algorithm is about as hopelessly inefficient as it could
possibly be, barring deliberate intent. [1]
3) You are running Python 2.x; unless you have a good reason not to,
it's better to use Python 3.
4) You're running as root. Normally, something like this should be run
as a regular user - it's safer that way.

Err, *amongst* the things to note are such diverse elements as...
etcetera, etcetera. Ahem.

I would suggest rewriting this as a much more straight-forward loop;
begin at the beginning, go on till you reach the point you wanted,
then stop.

ChrisA

[1] Cue the demonstration of a worse version from someone's student?

[toc] | [next] | [standalone]

#87854

On Tue, 24 Mar 2015 03:16 am, Chris Angelico wrote about the standard
recursive version of the Fibonacci series:

> On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal <ganesh1pal@gmail.com> wrote:

>> def fib(n):
>>     if n == 0:
>>         return 0
>>     elif n == 1:
>>         return 1
>>     else:
>>         return fib(n-1) + fib(n-2)


> 2) Your algorithm is about as hopelessly inefficient as it could
> possibly be, barring deliberate intent.


It is pretty inefficient, but it is a good toy example of recursion. It's
also a good example of how *not* to write the Fibonacci series in practice,
what is mathematically straightforward is not always computationally
efficient.

The question is, just how inefficient is is? How many calls to `fib` are
made in calling fib(n)?

Answer to follow.



-- 
Steven

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

#87857

On 03/23/2015 08:19 PM, Steven D'Aprano wrote:
> On Tue, 24 Mar 2015 03:16 am, Chris Angelico wrote about the standard
> recursive version of the Fibonacci series:
>
>> On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal <ganesh1pal@gmail.com> wrote:
>
>>> def fib(n):
>>>      if n == 0:
>>>          return 0
>>>      elif n == 1:
>>>          return 1
>>>      else:
>>>          return fib(n-1) + fib(n-2)
>
>
>> 2) Your algorithm is about as hopelessly inefficient as it could
>> possibly be, barring deliberate intent.
>
>
> It is pretty inefficient, but it is a good toy example of recursion. It's
> also a good example of how *not* to write the Fibonacci series in practice,
> what is mathematically straightforward is not always computationally
> efficient.
>
> The question is, just how inefficient is is? How many calls to `fib` are
> made in calling fib(n)?
>
> Answer to follow.
>
>
>

0 1
1 1
2 3
3 5
4 9
5 15
6 25
7 41
8 67
9 109
10 177
11 287
12 465
13 753
14 1219



-- 
DaveA

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

#87858

Given the standard recursive version of the Fibonacci series:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

I asked:

> The question is, just how inefficient is is? How many calls to `fib` are
> made in calling fib(n)?

The answer follows the spoiler space. Try solving the question yourself
before reading the answer.



*
*
*
*
*


 
S
P
O
I
L
E
R


 
S
P
A
C
E


 
*
*
*
*
*



fib(0) makes no recursive calls, so the answer for n = 0 is 1.

fib(1) makes no recursive calls, so the answer for n = 1 is 1.

fib(2) makes two recursive calls, fib(1) and fib(0), so the answer 
for n = 2 is 3.

fib(3) makes two recursive calls, fib(2) and fib(1). They in turn make 3 and
1 calls each, so the answer is 5:
    1 for the call to fib(3)
    +3 for the call to fib(2)
    +1 for the call to fib(1)

fib(4) makes two recursive calls, fib(3) and fib(2), giving 9 calls in
total:
    1 for the call to fib(4)
    +5 for the call to fib(3)
    +3 for the call to fib(2)

This is a recursive relationship very similar to the Fibonacci series! Let's
call the function "number of subroutine calls made by fib(n)" L(n), for
reasons which will become clear later:

def L(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return L(n-1) + L(n-2) + 1


This number grows significantly faster than the Fibonacci series itself.
Here are the first few values:

---  --------  ---------
n    Fib(n)    L(n)
---  --------  ---------
0    0         1
1    1         1
2    1         3
3    2         5
4    3         9
5    5         15
6    8         25
7    13        41
8    21        67
9    34        109
10   55        177
11   89        289
12   144       465
...
35   9227465   29860703
---  --------  ---------


L(n) is in fact a standard mathematical sequence, the nth Leonardo Number.


What if we ask the same question of Leo, that is, how many function calls
does Leo(n) make?

The number of function calls needed to calculate the nth Leonardo Number
using this recursive algorithm is ... the nth Leonardo Number. So in a way,
we need not actually bother calculating anything, but just count the number
of function calls, throwing away the intermediate results! I think that is
rather neat.

http://en.wikipedia.org/wiki/Leonardo_number



-- 
Steven

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

#87859

On Tue, Mar 24, 2015 at 11:19 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> It is pretty inefficient, but it is a good toy example of recursion. It's
> also a good example of how *not* to write the Fibonacci series in practice,
> what is mathematically straightforward is not always computationally
> efficient.
>
> The question is, just how inefficient is is? How many calls to `fib` are
> made in calling fib(n)?
>
> Answer to follow.

Exact answer not particularly important (though fun to calculate).
Practical answer: A *lot*. :)

I've never thought of the mathematical definition as being inherently
recursive; but as inherently sequential. Sure, you can define counting
numbers based on sets (0 is the cardinality of the empty set, 1 is the
cardinality of the set containing the empty set, et-set-era), but most
people will define them by counting. The Fibonacci sequence is
logically defined by starting somewhere and then adding to the
sequence. Yes, you can define it recursively too, but it's just as
easy to define it as a progression.

(Conversely, the squares *can* be defined as a progression - you add
the next odd number to the previous square - but they're more
logically defined by their indices. Some work better one way, some the
other way.)

Of course, mathematics works quite happily with infinity. You can
construct infinite sequences and do arithmetic on them, which
computers have a lot of trouble with. You can define anything in terms
of anything, no matter how long a chain of definitions it takes. And
above all, you can reduce problems to previously-solved states, which
implies that mathematics has a concept of caching. :)

ChrisA

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

#87861

On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:


> I've never thought of the mathematical definition as being inherently
> recursive; but as inherently sequential. Sure, you can define counting
> numbers based on sets (0 is the cardinality of the empty set, 1 is the
> cardinality of the set containing the empty set, et-set-era), but most
> people will define them by counting. The Fibonacci sequence is
> logically defined by starting somewhere and then adding to the
> sequence. Yes, you can define it recursively too, but it's just as
> easy to define it as a progression.

But what are you adding? You're not adding a constant or simple expression
each time, but a previous term of the series. That's recursion. The
mathematical term is that it is a recurrence relation, and is usually
written:

F[n] = F[n-1] + F[n-2]

where F[x] means F subscript x. In English: the nth Fibonacci number is
equal to the sum of the previous two Fibonacci numbers (with the first and
second given by 0 and 1 respectively). That's inherently recursive: the
definition is given in terms of itself.

http://en.wikipedia.org/wiki/Fibonacci_number

There is at least one closed-form (non-recursive) formula for Fibonacci
numbers, Binet's Formula:

F[n] = (φ**n - ψ**n)/sqrt(5)

where:

  φ is the Golden Ratio (1+sqrt(5))/2

  ψ = 1-φ

but that's not how the Fibonacci numbers are defined, or why they are
interesting. The Fibonacci numbers are just a special case for a more
mathematically interesting family of recurrence relations, the Lucas
sequences.

(Aside: due to floating point rounding, Binet's Formula will give inaccurate
results for large enough values of n. With n=77 it is off by 1.)

The important thing here is that all these associated sequences -- Fibonacci
numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are
defined as recurrences, i.e. recursively. But that doesn't necessarily make
recursion the best way to implement it.



-- 
Steven

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

#87862

On Tuesday, March 24, 2015 at 7:22:25 AM UTC+5:30, Steven D'Aprano wrote:
> On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:
> 
> 
> > I've never thought of the mathematical definition as being inherently
> > recursive; but as inherently sequential. Sure, you can define counting
> > numbers based on sets (0 is the cardinality of the empty set, 1 is the
> > cardinality of the set containing the empty set, et-set-era), but most
> > people will define them by counting. The Fibonacci sequence is
> > logically defined by starting somewhere and then adding to the
> > sequence. Yes, you can define it recursively too, but it's just as
> > easy to define it as a progression.
> 
> But what are you adding? You're not adding a constant or simple expression
> each time, but a previous term of the series. That's recursion. The
> mathematical term is that it is a recurrence relation, and is usually
> written:
> 
> F[n] = F[n-1] + F[n-2]
> 
> where F[x] means F subscript x. In English: the nth Fibonacci number is
> equal to the sum of the previous two Fibonacci numbers (with the first and
> second given by 0 and 1 respectively). That's inherently recursive: the
> definition is given in terms of itself.
> 
> http://en.wikipedia.org/wiki/Fibonacci_number
> 
> There is at least one closed-form (non-recursive) formula for Fibonacci
> numbers, Binet's Formula:
> 
> F[n] = (φ**n - ψ**n)/sqrt(5)
> 
> where:
> 
>   φ is the Golden Ratio (1+sqrt(5))/2
> 
>   ψ = 1-φ
> 
> but that's not how the Fibonacci numbers are defined, or why they are
> interesting. The Fibonacci numbers are just a special case for a more
> mathematically interesting family of recurrence relations, the Lucas
> sequences.
> 
> (Aside: due to floating point rounding, Binet's Formula will give inaccurate
> results for large enough values of n. With n=77 it is off by 1.)
> 
> The important thing here is that all these associated sequences -- Fibonacci
> numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are
> defined as recurrences, i.e. recursively. But that doesn't necessarily make
> recursion the best way to implement it.

I think (guess) Chris is saying that recurrence relations are somehow 'less
recursive' than recursion?

I find that view weird... though I should admit to making a similar one:

Recursion is not hard; its recursion mixed with imperative programming that's
a mismatch and therefore seems hard:
http://blog.languager.org/2012/10/functional-programming-lost-booty.html

The other unsatisfactory aspect of above discussion is that it seems to assume
recursion = recursive function

What about recursive data? eg the C list definition: ??

struct node {
int elem;
struct node *next;
};

In fact that's not just recursive its mutually recursive. Becomes evident
if rewritten as

typedef struct node *nodeptr;

struct node {
int elem;
nodeptr next;
};

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

#87863

On Tue, Mar 24, 2015 at 12:52 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:
>
>
>> I've never thought of the mathematical definition as being inherently
>> recursive; but as inherently sequential. Sure, you can define counting
>> numbers based on sets (0 is the cardinality of the empty set, 1 is the
>> cardinality of the set containing the empty set, et-set-era), but most
>> people will define them by counting. The Fibonacci sequence is
>> logically defined by starting somewhere and then adding to the
>> sequence. Yes, you can define it recursively too, but it's just as
>> easy to define it as a progression.
>
> But what are you adding? You're not adding a constant or simple expression
> each time, but a previous term of the series. That's recursion.

That's true, if you are defining "the Nth Fibonacci number". But if
you're defining "the Fibonacci sequence", then it's self-referential,
but not double-recursive as it is in the naive functional definition.
And that's where the problem comes from; it's pretty easy to handle a
single level of recursion by converting it to tail recursion, then
trivially converting that to iteration; double recursion is harder to
handle. The cache-append solution that Terry posted is basically
"evaluate the Fibonacci sequence up as far as we need it, then return
that number", which is what I'm talking about.

Mathematics doesn't like defining sequences, except by defining
functions, and so it has to convert the concept of "defining the
Fibonacci sequence" into "defining a function F(N) which returns the
Nth Fibonacci number", and that's where the double recursion comes
from. It's not an inherent part of the sequence, which is, uhh,
sequential.

ChrisA

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

#87864

On Tuesday, March 24, 2015 at 8:33:24 AM UTC+5:30, Chris Angelico wrote:
> On Tue, Mar 24, 2015 at 12:52 PM, Steven D'Aprano wrote:
> > On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:
> >
> >
> >> I've never thought of the mathematical definition as being inherently
> >> recursive; but as inherently sequential. Sure, you can define counting
> >> numbers based on sets (0 is the cardinality of the empty set, 1 is the
> >> cardinality of the set containing the empty set, et-set-era), but most
> >> people will define them by counting. The Fibonacci sequence is
> >> logically defined by starting somewhere and then adding to the
> >> sequence. Yes, you can define it recursively too, but it's just as
> >> easy to define it as a progression.
> >
> > But what are you adding? You're not adding a constant or simple expression
> > each time, but a previous term of the series. That's recursion.
> 
> That's true, if you are defining "the Nth Fibonacci number". But if
> you're defining "the Fibonacci sequence", then it's self-referential,
> but not double-recursive as it is in the naive functional definition.

Here are two different approaches for 2nd order recurrence to 1st order:

# input recursion
def fibir(n, a=0, b=1):
    return ( a if n==0   else
             b if n==1   else
             fibir(n-1, b, a+b)
           )

# Output recursion
def fibor(n):
    if n==0:
        return (0,1)
    else:
        (a,b) = fibor(n-1)
        return (b,a+b)



> And that's where the problem comes from; 

What problem?
I see the problem starting with the fact that we treat a math-defn
as a computational one.

> it's pretty easy to handle a
> single level of recursion by converting it to tail recursion, then
> trivially converting that to iteration; double recursion is harder to
> handle. The cache-append solution that Terry posted is basically
> "evaluate the Fibonacci sequence up as far as we need it, then return
> that number", which is what I'm talking about.
> 
> Mathematics doesn't like defining sequences, except by defining
> functions, and so it has to convert the concept of "defining the
> Fibonacci sequence" into "defining a function F(N) which returns the
> Nth Fibonacci number", and that's where the double recursion comes
> from. It's not an inherent part of the sequence, which is, uhh,
> sequential.
> 
> ChrisA

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

#87865

On Tuesday, March 24, 2015 at 8:33:24 AM UTC+5:30, Chris Angelico wrote:
> Mathematics doesn't like defining sequences, except by defining
> functions, and so it has to convert the concept of "defining the
> Fibonacci sequence" into "defining a function F(N) which returns the
> Nth Fibonacci number", and that's where the double recursion comes
> from. It's not an inherent part of the sequence, which is, uhh,
> sequential.

Here is a pure 'recursive-data' definition of fib.
[Of course assuming you can buy that generators are data not functions]

==================
from itertools import tee

def fib():
    yield 0
    yield 1
    f, fn = tee(fib())
    next(fn)
    yield from (x+y for (x,y) in zip(f, fn))

The fact that this is data may be more clear if you see it as a rendering
(uglification) of the Haskell list-definition

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[toc] | [prev] | [standalone]

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

csiph-web