Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!newsfeed.eweka.nl!eweka.nl!feeder3.eweka.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=cUCOi86gBDMlZ31p2W5FJ807dYGw82ytwYpznJKBsnSwUFCSK1UkywiT3Jfyowj6RL yiilK0A4aPen7Onv6FqzEDpjLVaoemvVfsRwued0Q0yI9H09EEzjI6159Dux4rs1umTa GIaJ2Yj2DFu103bUwhT7bNEcAWGJw+oRAj9to=
MIME-Version: 1.0
In-Reply-To: <6fs198-8lf.ln1@svn.schaathun.net>
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>
Date: Mon, 2 May 2011 16:28:45 +1000
Subject: Re: Fibonacci series recursion error
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1057.1304317729.9059.python-list@python.org>
Lines: 54
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:4441

On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun <hg@schaathun.net> wro=
te:
> On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
> =A0<rosuav@gmail.com> wrote:
> : =A0Sure. Serialize this Python object in a way that can be given to, sa=
y, PHP:
> : =A0foo=3D{"asdf":"qwer","zxcv":"1234"}; foo["self"]=3D[1,2,3,foo]
>
> Wouldn't cyclic references give infinite recursion? =A0And 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). Since every
element in the dictionary can be a list/dict, and every element of
those can be too, there's no non-recursive way to do it, other than by
doing the recursion yourself:

# partly pseudocode
searchme=3D[foo]
while len(searchme):
  cur=3Dget_next_elem(searchme[-1])
  if cur=3D=3Dend_of_list: searchme[-1:]=3D[]
  else: if can_be_recursed_into(cur): searchme.append(cur)
  else: output(cur)

This would work, more or less, but it merely trades "true" recursion
for the searchme[] stack. Yes, it's iterative. No, it hasn't abolished
recursion.

> True. =A0There is a place for everything. =A0However, in the example
> above, you can map the recursive definition directly into python
> without further ado. =A0In order to express the one-liner in python,
> as iteration, you need to introduce additional elements, namely
> a state (index variable). =A0Hence, recursion is clearer by being
> close to the language you would normally use to describe the
> problem.

True, and you could abolish a lot of temporary variables by turning
them into parameters to recursive calls. But you've abolished nothing.

The recursive factorial is very similar to:
reduce(`*,range(1,n+1))
The iterative is very similar to:
reduce(`*,xrange(1,n+1))
One of 'em stacks up all the numbers and the other gets 'em as it
needs 'em. Fundamentally, there's really not a lot of difference. By
piling up the numbers on your stack, you just change the format of
your saved state, you don't actually save anything.

Chris Angelico