Re: Fibonacci series recursion error

From	Hans Georg Schaathun <hg@schaathun.net>
Newsgroups	comp.lang.python
Subject	Re: Fibonacci series recursion error
Date	2011-05-02 06:36 +0100
Organization	University of Bergen
Message-ID	<6fs198-8lf.ln1@svn.schaathun.net> (permalink)
References	(8 earlier) <4dbd221a$0$29991$c3e8da3$5496439d@news.astraweb.com> <iklv88-nba.ln1@svn.schaathun.net> <4dbd4a88$0$29991$c3e8da3$5496439d@news.astraweb.com> <n03098-4qc.ln1@svn.schaathun.net> <mailman.1046.1304282984.9059.python-list@python.org>

Show all headers | View raw

On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
  <rosuav@gmail.com> wrote:
:  Sure. Serialize this Python object in a way that can be given to, say, PHP:
:  foo={"asdf":"qwer","zxcv":"1234"}; foo["self"]=[1,2,3,foo]
:  Recurse from self into the list, recurse from there into a
:  dictionary... Okay, that's a rather naive recursion and fraught with
:  risk, but there are more complex examples. And watching for cyclic
:  references would be O(N*N) as you'd need to maintain a full list of
:  every PyObject* that you've sighted (talking here from the C API, but
:  the same consideration applies whichever way you do it).

Wouldn't cyclic references give infinite recursion?  And remain
infinitive if you recode it iteratively?

:  I'm not sure that recursion is clearer. Recursion is a way of
:  expressing the two rules:
: 
:  1! = 1
:  n! = n * (n-1)!
: 
:  But iteration is a way of expressing this equivalent rule:
: 
:  n! = 1 * 2 * 3 * ... * n-1 * n
: 
:  It really depends what you're trying to say.

True.  There is a place for everything.  However, in the example
above, you can map the recursive definition directly into python
without further ado.  In order to express the one-liner in python,
as iteration, you need to introduce additional elements, namely
a state (index variable).  Hence, recursion is clearer by being
close to the language you would normally use to describe the
problem.

-- 
:-- Hans Georg

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

Thread

Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 15:40 +0100
  Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 09:18 +0100
    Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 09:04 +0000
      Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 10:27 +0100
        Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 11:56 +0000
          Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 14:15 +0100
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 06:49 +1000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 06:36 +0100
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:28 +1000
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:30 +1000
                Re: Fibonacci series recursion error (slightly OT) Dave Angel <davea@ieee.org> - 2011-05-02 08:50 -0400
            Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 01:09 +0000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 10:41 +0100
        Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-01 18:24 -0400
          Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 14:14 +0100
            Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 16:41 +0000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 21:02 +0100
                Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 00:21 +0000
                Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 20:42 -0700
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 06:13 +0100
                Re: Fibonacci series recursion error Robert Brown <robert.brown@gmail.com> - 2011-05-08 01:44 -0400
            Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-02 14:56 -0400
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 07:56 +1000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 08:01 +0100

csiph-web