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
--
https://mail.python.org/mailman/listinfo/python-list
