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

Oscar Benjamin oscar.j.benjamin at gmail.com
Thu Sep 12 11:57:18 CEST 2013

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:

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


More information about the Python-ideas mailing list