On 12 September 2013 05:29, Joshua Landau joshua@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%27s_strongly_connected_components_algori...
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