Fibonacci series recursion error

Hans Georg Schaathun hg at schaathun.net
Mon May 2 01:36:06 EDT 2011


On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
  <rosuav at 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



More information about the Python-list mailing list