Re: Fibonacci series recursion error (slightly OT)

Date	2011-05-02 08:50 -0400
From	Dave Angel <davea@ieee.org>
Subject	Re: Fibonacci series recursion error (slightly OT)
References	(10 earlier) <4dbd4a88$0$29991$c3e8da3$5496439d@news.astraweb.com> <n03098-4qc.ln1@svn.schaathun.net> <mailman.1046.1304282984.9059.python-list@python.org> <6fs198-8lf.ln1@svn.schaathun.net> <BANLkTin2Z1Y8Ht0xe+5b2539TNAKpRMhag@mail.gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.1071.1304340996.9059.python-list@python.org> (permalink)

Show all headers | View raw

On 01/-10/-28163 02:59 PM, Chris Angelico wrote:
> On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun<hg@schaathun.net>  wrote:
>> 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]
>>
>> Wouldn't cyclic references give infinite recursion?  And remain
>> infinitive if you recode it iteratively?
>
> Well, I don't know of a decent non-recursive way to process a
> recursive structure. Incidentally, this example is almost directly
> from some working code of ours; I have a C function that recurses over
> a Python dictionary and aborts as soon as it's found "too much" data
> (for a fairly arbitrary definition of "too much", but one that's
> deliberately designed to prevent infinite recursion).
> <snip>
>
> Chris Angelico
>

When iterating over a repeatable, potentially infinite sequence of 
distinguishable values, you can safely detect infinitude ;-)  (cycles) 
with a linear overhead (rather than n-squared).

Given a sequence, create two iterators for it.  Start them both at the 
same point, but iterate the second one twice for every time you iterate 
the first one.  If the two ever get the same value, you have a cycle.

In the case of Python objects, you probably want to use an 'is' 
comparison, rather than comparing id() for equal.  But the concept 
works, and easily.

DaveA

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 Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-08 12:59 +0000
                Development time vs. runtime performance (was: Fibonacci series recursion error) Teemu Likonen <tlikonen@iki.fi> - 2011-05-08 19:34 +0300
                Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-09 12:49 +1000
                Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Robert Brown <robert.brown@gmail.com> - 2011-05-08 23:01 -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