On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun <h...@schaathun.net> wrote:
> On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
> <ros...@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). 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=[foo]
while len(searchme):
cur=get_next_elem(searchme[-1])
if cur==end_of_list: searchme[-1:]=[]
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. 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.
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
--
http://mail.python.org/mailman/listinfo/python-list
