Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <SRS0=Fj20=XY=ieee.org=davea@srs.perfora.net>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.000
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'value,': 0.04; 'sure.': 0.05; 'decent': 0.07; 'dictionary': 0.07; 'infinite': 0.07; 'linear': 0.07; 'python': 0.07; '(rather': 0.09; 'deliberately': 0.09; 'iterate': 0.09; 'structure.': 0.09; 'values,': 0.09; 'pm,': 0.11; 'subject:error': 0.12; ';-)': 0.14; 'say,': 0.14; 'skip:f 30': 0.14; 'wrote:': 0.14; 'cyclic': 0.16; 'equal.': 0.16; 'php:': 0.16; 'recursive': 0.16; 'sequence,': 0.16; "wouldn't": 0.18; 'comparing': 0.19; 'cc:no real name:2**0': 0.20; 'cc:2**0': 0.20; 'code': 0.22; 'header:In-Reply-To:1': 0.22; 'cc:addr:python-list': 0.22; 'mon,': 0.22; 'objects,': 0.23; 'example': 0.24; 'detect': 0.25; 'point,': 0.25; 'chris': 0.27; 'object': 0.27; 'function': 0.27; 'definition': 0.29; 'probably': 0.30; 'cc:addr:python.org': 0.31; 'iterating': 0.31; 'second': 0.31; 'it.': 0.31; 'fairly': 0.33; '(for': 0.33; 'received:192.168.1': 0.34; 'received:192': 0.34; 'header:User-Agent:1': 0.35; 'overhead': 0.35; 'safely': 0.35; 'rather': 0.36; 'data': 0.37; 'received:192.168': 0.37; 'two': 0.37; 'some': 0.37; 'case': 0.37; 'references': 0.38; 'sequence': 0.38; 'but': 0.38; 'subject: (': 0.39; "it's": 0.40; 'twice': 0.60; 'give': 0.61; '2011': 0.62; 'ever': 0.65; 'received:perfora.net': 0.68; 'works,': 0.69; 'designed': 0.69; 'reply-to:no real name:2**0': 0.72; 'header:Reply-To:1': 0.72; 'concept': 0.73; 'soon': 0.76; '02:59': 0.84; 'received:74.208.4.194': 0.84
Date: Mon, 02 May 2011 08:50:39 -0400
From: Dave Angel <davea@ieee.org>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.14) Gecko/20110223 Thunderbird/3.1.8
MIME-Version: 1.0
To: Chris Angelico <rosuav@gmail.com>
Subject: Re: Fibonacci series recursion error (slightly OT)
References: <a78a0ffd-03cc-4540-addb-b8e206d165d5@n2g2000prj.googlegroups.com>	<KtMup.29280$8U5.7734@newsfe20.iad> <87iptw1egh.fsf@rudin.co.uk>	<up6t88-4p7.ln1@svn.schaathun.net> <87ei4k0ygz.fsf@rudin.co.uk>	<mvet88-018.ln1@svn.schaathun.net> <87aaf7246f.fsf@rudin.co.uk>	<sjhv88-r7a.ln1@svn.schaathun.net>	<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>	<6fs198-8lf.ln1@svn.schaathun.net> <BANLkTin2Z1Y8Ht0xe+5b2539TNAKpRMhag@mail.gmail.com>
In-Reply-To: <BANLkTin2Z1Y8Ht0xe+5b2539TNAKpRMhag@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Provags-ID: V02:K0:SJALNvrgwyeynjSXs4P+bVQjnyvnwLXoGPeAdXeQWg6 rl9AMX/zLDeT+z7xVsOm73zzGbilxW0Z/mUMrXtpdH3Cj6N5bK u3vnG2qH82BTfABO4PLwobuThbF3GnbGj7/h5dS1pIqtDbOtiH kXfEZzjuGZih0cHikxUUZNxaA/Y+6ZOeaVVJ6dXzvfT9cvL1Ff vifT9HSfnVX8tJxG14GHw==
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
Reply-To: davea@ieee.org
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.1071.1304340996.9059.python-list@python.org>
Lines: 34
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1304340997 news.xs4all.nl 81485 [::ffff:82.94.164.166]:43979
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:4476

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