On Sun, May 1, 2011 at 11:15 PM, Hans Georg Schaathun <h...@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
--
http://mail.python.org/mailman/listinfo/python-list
