Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <5510c34c$0$12999$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> <mailman.90.1427158790.10327.python-list@python.org> <5510c34c$0$12999$c3e8da3$5496439d@news.astraweb.com>
Date: Tue, 24 Mar 2015 14:03:05 +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.92.1427166194.10327.python-list@python.org>
Lines: 35
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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