[Python-ideas] FW: Idea: Compressing the stack on the fly

[Oscar Benjamin]

On 12 September 2013 05:29, Joshua Landau <joshua at landau.ws> wrote:
> Does anyone actually write recursive Python code where the recursion
> in a significant bottleneck? The only such code I can think of is
> either for a tree, in which case stack depth is irrelevant, or bad
> code.
>
> Why would anyone care, basically?

I think you're asking this question the wrong way. Recursion isn't a
bottleneck that slows down your program. When you hit the recursion
limit your program just blows up. Since Python doesn't have the
optimisations that make any particular kind of recursion scale well
people do not generally use it unless they know that the depth is
small enough. Currently code that is susceptible to hitting the
recursion limit is "bad code" because it depends on optimisations that
don't exist. However, if the optimisations did exist then people could
choose to take advantage of them.

As an example, I once implemented Tarjan's algorithm in Python using
the recursive form shown here:
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#The_algorithm_in_pseudocode

After implementing it and confirming that it worked I immediately
found that it hit the recursion limit in my real problem. So I
reimplemented it without the recursion. Had there been optimisations
that would have made the reimplementation unnecessary I would have
happily stuck with the first form since it was easier to understand
than the explicit stack of iterators version that I ended up with. For
the same reasons you won't see much code out there where recursion is
a bottleneck unless, as you say, it is "bad code".


Oscar