Fibonacci series recursion error (slightly OT)

[Dave Angel]

On 01/-10/-28163 02:59 PM, Chris Angelico wrote:
> On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun<hg at schaathun.net>  wrote:
>> 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]
>>
>> 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