Fibonacci series recursion error

[Chris Angelico]

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