Fibonacci series recursion error

[Chris Angelico]

On Sun, May 1, 2011 at 11:15 PM, Hans Georg Schaathun <hg at schaathun.net> wrote:
> :  The Python virtual machine knows how big each entry on the stack needs to
> :  be. (I don't, but it's got to be at least the size of a pointer.) So
> :  "number of items" is just a multiplication away from "size of the items".
>
> Does it?  In a conventional stack you need to store all the local
> variables for the function as well.  Thus, there is no limit to how
> much space a single element on the stack may require.

In anything less than a useless and trivial demo of recursion, there's
going to be some kind of local state for each call (in the case of a
fibonacci or factorial, that would be the number(s) being multiplied).
Whether they go on the stack or elsewhere, that's additional storage
that gets multiplied out.

> There is also a limit to how far you can usefully recurse over a limited
> data structure.

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]
Recurse from self into the list, recurse from there into a
dictionary... Okay, that's a rather naive recursion and fraught with
risk, but there are more complex examples. And watching for cyclic
references would be O(N*N) as you'd need to maintain a full list of
every PyObject* that you've sighted (talking here from the C API, but
the same consideration applies whichever way you do it).

> There are many ways to crash a system if you want to.
>
> But if you don't deliberately try to crash it, you are much more
> likely to crash it because you allocate to much memory in each step
> than because the recursion gets to deep.  Consequently, because recursion
> is usually a clearer form of expression than iterative loops, recursion
> may actually be /less/ dangerous.

I'm not sure that recursion is clearer. Recursion is a way of
expressing the two rules:

1! = 1
n! = n * (n-1)!

But iteration is a way of expressing this equivalent rule:

n! = 1 * 2 * 3 * ... * n-1 * n

It really depends what you're trying to say.

Chris Angelico