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

On 12 September 2013 09:34, M.-A. Lemburg wrote:

On 12.09.2013 09:03, Joshua Landau wrote:

...

On 12 September 2013 07:59, M.-A. Lemburg wrote:

...

On 12.09.2013 06:29, Joshua Landau 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.

Any kind of backtracking algorithm will need recursion or a separate stack data structure to keep track of the various decisions made up to a certain point on the path.

The C stack is rather limited in size, so a recursive parser can easily blow up if it uses the C stack alone for managing backtracking.

What sort of algorithm would backtrack that many times? I doubt a parser would and I can't think of anything worse ATM.

Oh, that's easy. It just depends on the given data set that you're working on and how often you have to branch when working on it.

http://en.wikipedia.org/wiki/Backtracking lists a few problems.

Here's a regular expression example that would blow the stack, if the re module were still using it (it was fixed in 2003 to no longer do):

re.match('(.*a|.*b|x)+', 'x' * 100000)

The expression still uses exponential time, though.

Ah, Regex. 'Could'a guessed. I'll file that under "bad code". *wink*