Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4441

Re: Fibonacci series recursion error

Show key headers only | View raw

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). 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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