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

Groups > comp.lang.python > #87859

Re: fibonacci series what Iam is missing ?

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web