"ulimit -s" has no effect?

Josiah Carlson jcarlson at nospam.uci.edu
Sat Feb 7 20:49:48 CET 2004


> Interesting.  Alas, I don't think I can use this.  First, this seems to only
> apply to tail recursion, no?  In the Tarjan's algorithm recursion happens at
> the beginning, on the children of a given node, and then the results of that
> recursion are used in the computation for the current node.  Also, I think my
> locals() won't be "sane"... it contains a huge graph; from what I understand
> from the above, there would be multiple copies of it on `stack', and that's
> just not feasible due to memory constraints.

Though it sometimes takes work, _any_ recursive algorithm can be made 
iterative.  If you are willing to cough up your code (via email or 
otherwise), I'd be willing to give a shot at converting it.

As an example, DFS is not tail recursive, but I've converted a DFS 
algorithm for generating a browsable source tree for PyPE 
(pype.sourceforge.net).

In terms of your question about it keeping multiple copies of objects on 
the stack, really it only keeps multiple /references/ to objects on the 
stack.  Python 2.2+ standard nested scopes does the same thing.  The 
only difference is that we use a list as a call stack, rather than 
relying on the C stack for the Python call stack, which is what is 
limiting your program.

So yeah, want me to give the conversion a shot?
  - Josiah



More information about the Python-list mailing list