32

I've made a small function that will actually measure the max recursion limit:

def f(x):
    r = x
    try:
        r = f(x+1)
    except Exception as e:
        print(e)
    finally:
        return r

To know what to expect I've checked:

In [28]: import sys

In [29]: sys.getrecursionlimit()
Out[29]: 1000

However

In [30]: f(0)
maximum recursion depth exceeded
Out[30]: 970

The number is not fixed, always around ~970, and slightly changes between different instances of python (e.g. from within spyder to system cmd prompt).

Please note that I'm using ipython on python3.

What's going on? Why is the actual limit I'm getting lower than the sys.getrecursionlimit() value?

Aguy
  • 7,851
  • 5
  • 31
  • 58
  • It is a guard against a stack overflow. You can change the recursion limit with `sys.setrecursionlimit`, but doing so is dangerous. – dazzieta Jul 08 '16 at 11:51
  • 1
    What happens when you manually set the recursionlimit using `sys.setrecursionlimit(limit)` (https://docs.python.org/3/library/sys.html#sys.setrecursionlimit) at the beginning of your code? See also http://stackoverflow.com/questions/3323001/maximum-recursion-depth and http://stackoverflow.com/questions/5061582/setting-stacksize-in-a-python-script/16248113#16248113 – linusg Jul 08 '16 at 11:52
  • 2
    Just a side note. You shouldn't fix your recursive code by raising the recursion limit, because that is not load-proof. If you really want recursion, then use TCO and a decorator to eliminate the tail calls (there are plenty). Or just stick with an imperative alternative. – Eli Korvigo Jul 08 '16 at 11:53
  • 1
    @utkarsh13 - just wrote that before you :) – linusg Jul 08 '16 at 11:56
  • 2
    @EliKorvigo I don't really see the point of using a tco decorator. They introduce a lot of overhead. Moreover given any tail-code recursive definition it is **trivial** to convert it into an iterative definition... so just use the iterative solution. – Bakuriu Jul 08 '16 at 12:00
  • @Bakuriu that's why I wrote "Or just stick with an imperative alternative", though some of us readily pay the overhead for the functional purity. – Eli Korvigo Jul 08 '16 at 12:10
  • What happens when you add more parameters to the function? I suspect you get the exception sooner, because more needs to be pushed onto the stack for each recursion. Or no params and increase some global value. – Hans Kesting Jul 08 '16 at 13:30

3 Answers3

38

The recursion limit is not the limit on recursion but the maximum depth of the python interpreter stack.There is something on the stack before your function gets executed. Spyder executes some python stuff before it calls your script, as do other interpreters like ipython.

You can inspect the stack via methods in the inspect module.

In CPython for me:

>>>print(len(inspect.stack()))
1

In Ipython for me:

>>>print(len(inspect.stack()))
10

As knbk pointed out in the comments as soon as you hit the stack limit a RecursionError is thrown and the interpreter raises the stack limit a bit to give you a possibility to handle the error gracefully. If you also exhaust that limit python will crash.

syntonym
  • 7,134
  • 2
  • 32
  • 45
  • 1
    Great stuff. I get in Ipython console a stack of 23. But shouldn't then `len(inspect.stack()) + f(0) == sys.getrecursionlimit()`? Because I'm still 7 stack items short... :-) – Aguy Jul 08 '16 at 12:05
  • What happens if you `print(inspect.stack())` when you except the exception? – syntonym Jul 08 '16 at 12:07
  • If I `print(inspect.stack())` inside the exception I get 994. Close enough to the 7 stack items missing (my function may have a +1 issue which I didn't fully weed out). But then why is an exception being raised? the stack is only 994 full... – Aguy Jul 08 '16 at 12:13
  • 1
    @Theguy the function call, that results in the ecxeption, is already removed from the stack by the time you catch the exception and it can be traced in the traceback of the exception object. You can make your function report the stack size before each recursive call and see the dynamics. – Eli Korvigo Jul 08 '16 at 12:31
  • @EliKorvigo But that shouldn't account for 5-6 frames, should it? – syntonym Jul 08 '16 at 12:35
  • You should remember: Your print(e) function will also need stack-space to work! So if you recurse down to f at stack 1000 - the call to f(1001) will fail. Then the call to print(e) will fail. And depending on the print implementation the method will maybe need 3-4 stack depth to actually write to the console ;-) ... So your call to print(e) will most likely fail 3-4 times until you are at 996 and it can work. – Falco Jul 08 '16 at 12:35
  • @Falco Ah, that makes sense! – syntonym Jul 08 '16 at 12:36
  • @Theguy @Falco Actually for me `f(0)` returns 998 regardless wether I use the code in the question or without any `print`s. – syntonym Jul 08 '16 at 12:47
  • 9
    @Falco Actually (at least in CPython), reaching the stack limit will set a flag and temporarily raise the stack limit (by 50, IIRC) to allow clean handling of the exception. If you reach the new stack limit while handling the exception, a fatal error will occur and your application will crash. Dropping under the first non-temporary limit by 50 or more will reset the flag and the limit, and reaching it again will create a new exception rather than a fatal error. So no, the call to `print(e)` will not fail. – knbk Jul 08 '16 at 13:15
  • @knbk - great insight. Indeed this is simple code will crash python. Call back the recursion in the except. `def f(num): try: return f(num) except: return f(num)`. Python will die a horrible death. – Aguy Jul 09 '16 at 14:32
9

This limit is for stack, not for the function you define. There are other internal things which might push something to stack.

And of course it could depend on env in which it was executed. Some can pollute stack more, some less.

Viacheslav Kondratiuk
  • 8,493
  • 9
  • 49
  • 81
6

I believe the confusion originates from the difference between the stack size you see when the error occurs and the limit. The thing is that the last call, that caused the crash, likely accounts for more than 1 frame on the stack, because it itself makes some function calls. And by the time you catch the exception, the call and its internal calls will have been removed from the stack. You can actually see them in the traceback. Let's look at this one. 

In [1]: import inspect

In [2]: import sys

In [3]: sys.setrecursionlimit(50)  # I'm setting this to 50 to make the traceback shorter.

In [4]: stack_log = []

In [5]: def recur():
    stack_log.append(len(inspect.stack()))
    recur()
   ...:     

In [6]: recur()

We get the traceback (note: there is no need to read it now, so just move forward to the next section).

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-6-45136123341b> in <module>()
----> 1 recur()

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
----> 2     stack_log.append(len(inspect.stack()))
      3     recur()
      4 

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in stack(context)
   1462 def stack(context=1):
   1463     """Return a list of records for the stack above the caller's frame."""
-> 1464     return getouterframes(sys._getframe(1), context)
   1465 
   1466 def trace(context=1):

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getouterframes(frame, context)
   1439     framelist = []
   1440     while frame:
-> 1441         frameinfo = (frame,) + getframeinfo(frame, context)
   1442         framelist.append(FrameInfo(*frameinfo))
   1443         frame = frame.f_back

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getframeinfo(frame, context)
   1412         start = lineno - 1 - context//2
   1413         try:
-> 1414             lines, lnum = findsource(frame)
   1415         except OSError:
   1416             lines = index = None

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in findsource(object)
    742     is raised if the source code cannot be retrieved."""
    743 
--> 744     file = getsourcefile(object)
    745     if file:
    746         # Invalidate cache if needed.

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getsourcefile(object)
    670         return filename
    671     # only return a non-existent filename if the module has a PEP 302 loader
--> 672     if getattr(getmodule(object, filename), '__loader__', None) is not None:
    673         return filename
    674     # or it is in the linecache

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getmodule(object, _filename)
    699     # Try the cache again with the absolute file name
    700     try:
--> 701         file = getabsfile(object, _filename)
    702     except TypeError:
    703         return None

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getabsfile(object, _filename)
    683     if _filename is None:
    684         _filename = getsourcefile(object) or getfile(object)
--> 685     return os.path.normcase(os.path.abspath(_filename))
    686 
    687 modulesbyfile = {}

/Users/ilia/.venvs/py3/bin/../lib/python3.5/posixpath.py in abspath(path)
    355 def abspath(path):
    356     """Return an absolute path."""
--> 357     if not isabs(path):
    358         if isinstance(path, bytes):
    359             cwd = os.getcwdb()

/Users/ilia/.venvs/py3/bin/../lib/python3.5/posixpath.py in isabs(s)
     61 def isabs(s):
     62     """Test whether a path is absolute"""
---> 63     sep = _get_sep(s)
     64     return s.startswith(sep)
     65 

RecursionError: maximum recursion depth exceeded

What's with the stack log?

In [7]: stack_log[-1]
Out[7]: 39

Okay, we have 11 missing frames. Now, scroll down the traceback to the last recur call, i.e.

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
      2     stack_log.append(len(inspect.stack()))
----> 3     recur()
      4 

<ipython-input-5-643b16f38b2e> in recur()
      1 def recur():
----> 2     stack_log.append(len(inspect.stack()))
      3     recur()
      4 

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in stack(context)
   1462 def stack(context=1):
   1463     """Return a list of records for the stack above the caller's frame."""
-> 1464     return getouterframes(sys._getframe(1), context)
   1465 
   1466 def trace(context=1):

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getouterframes(frame, context)
   1439     framelist = []
   1440     while frame:
-> 1441         frameinfo = (frame,) + getframeinfo(frame, context)
   1442         framelist.append(FrameInfo(*frameinfo))
   1443         frame = frame.f_back

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getframeinfo(frame, context)
   1412         start = lineno - 1 - context//2
   1413         try:
-> 1414             lines, lnum = findsource(frame)
   1415         except OSError:
   1416             lines = index = None

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in findsource(object)
    742     is raised if the source code cannot be retrieved."""
    743 
--> 744     file = getsourcefile(object)
    745     if file:
    746         # Invalidate cache if needed.

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getsourcefile(object)
    670         return filename
    671     # only return a non-existent filename if the module has a PEP 302 loader
--> 672     if getattr(getmodule(object, filename), '__loader__', None) is not None:
    673         return filename
    674     # or it is in the linecache

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getmodule(object, _filename)
    699     # Try the cache again with the absolute file name
    700     try:
--> 701         file = getabsfile(object, _filename)
    702     except TypeError:
    703         return None

/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/inspect.py in getabsfile(object, _filename)
    683     if _filename is None:
    684         _filename = getsourcefile(object) or getfile(object)
--> 685     return os.path.normcase(os.path.abspath(_filename))
    686 
    687 modulesbyfile = {}

/Users/ilia/.venvs/py3/bin/../lib/python3.5/posixpath.py in abspath(path)
    355 def abspath(path):
    356     """Return an absolute path."""
--> 357     if not isabs(path):
    358         if isinstance(path, bytes):
    359             cwd = os.getcwdb()

/Users/ilia/.venvs/py3/bin/../lib/python3.5/posixpath.py in isabs(s)
     61 def isabs(s):
     62     """Test whether a path is absolute"""
---> 63     sep = _get_sep(s)
     64     return s.startswith(sep)
     65 

RecursionError: maximum recursion depth exceeded

And here you are, there are exactly 11 function calls (the arrows on the left), that is 11 frames on the stack that were removed when the exception was raised.

Eli Korvigo
  • 10,265
  • 6
  • 47
  • 73