Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <5510ad7a$0$12979$c3e8da3$5496439d@news.astraweb.com>
References: <CACT3xuVF-MOVQK5wSorRSAfpAQEXvS7QsqarACVZKXsQ0bxzpQ@mail.gmail.com> <mailman.72.1427127417.10327.python-list@python.org> <5510ad7a$0$12979$c3e8da3$5496439d@news.astraweb.com>
Date: Tue, 24 Mar 2015 11:59:46 +1100
Subject: Re: fibonacci series what Iam is missing ?
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.90.1427158790.10327.python-list@python.org>
Lines: 37
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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