On 12.09.2013 09:03, Joshua Landau wrote:
On 12 September 2013 07:59, M.-A. Lemburg <mal@egenix.com> 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. With Python 2.3, you see the stack limit error: Python 2.3.5 (#1, Aug 24 2011, 15:52:42) [GCC 4.5.0 20100604 [gcc-4_5-branch revision 160292]] on linux2 Type "help", "copyright", "credits" or "license" for more information.
import re re.match('(.*a|.*b|x)+', 'x' * 100000) Traceback (most recent call last): File "<stdin>", line 1, in ? File "/usr/local/python-2.3-ucs2/lib/python2.3/sre.py", line 132, in match return _compile(pattern, flags).match(string) RuntimeError: maximum recursion limit exceeded
-- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Sep 12 2013)
Python Projects, Consulting and Support ... http://www.egenix.com/ mxODBC.Zope/Plone.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
2013-09-11: Released eGenix PyRun 1.3.0 ... http://egenix.com/go49 2013-09-04: Released eGenix pyOpenSSL 0.13.2 ... http://egenix.com/go48 2013-09-20: PyCon UK 2013, Coventry, UK ... 8 days to go eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48 D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg Registered at Amtsgericht Duesseldorf: HRB 46611 http://www.egenix.com/company/contact/