Trouble with try and except blocks with recursion

Question

I'm having trouble understanding the following:

import sys

def f(n):
    try:
        print('try', n)
        f(n + 1)
    except:
        print('except', n)
        if n > 0:
            raise

sys.setrecursionlimit(1000)
f(0)

It's output is:

try 0
try 1
try 2
...
try 995
except 996
except 995
...
except 0

I understand that the try block would iterate and print n until the systems recursion limit is met, in which case the except block is entered. My question is, in the except block, why is n decreasing and where is recursion occurring here? Furthermore, why does n not meet the recursion limit precisely? That is, why does the sequence not reach try 1000? Thanks!

Answer 1

1. Your first quesition on why you don't reach the recursion limit has been answered previously by Why Python raises RecursionError before it exceeds the real recursion limit? illustrates there are:

• recursion limit refers maximum depth of the stack frames
• there are frames on the stack before your function f is called
• other functions (such as the print you're using) places things on the stack
• you can use the inspect module to get the current depth of stack frame using len(inspect.stack()) as described in How do I get the current depth of the Python interpreter stack?

2. Regarding your second question of why the except numbers are decreasing:

• Your code creates a stack of calls:

  f(0)
    f(1)
      ...
      f(997)  # Exception is raised when you get to the stack limit
  

The code lines:

except:
    print('except', n)
        if n > 0:
            raise

The exception is reported to the parent and caught by the parents except block which: prints the value of n re-raises the exception (i.e. raise statement), passing it back to its parent

So we get the exception sequence of:

     f(996)  # receives except from f(1+996), prints 996, and raises exception to its parent
   f(995)  # receives exception from f(1+995) call, print 995, and raises exception to its parent
  ...
  f(1)  # receives exception from f(1+1) call, prints 1, and raises except to its aprent
 f(0) # receives exception from f(1+0) call and prints 0

Answer 2

when you get the exception in the deepest call you go to the except part, and print, that easy enough to understand, right?, then you raise again the same exception you got, now is the previous caller that get the exception and in turn go to except block and print and because it is the previous caller it will have the previous value of n and thus print one less, rinse a repeat, you are just walking back your recursive path

>>> sys.setrecursionlimit(5)
>>> f(0)
try 0
try 1
try 2
try 3
try 4
try 5
try 6
try 7
try 8
try 9
try 10
try 11
try 12
try 13
try 14
try 15
try 16
except 16
except 15
except 14
except 13
except 12
except 11
except 10
except 9
except 8
except 7
except 6
except 5
except 4
except 3
except 2
except 1
except 0
>>> 

And as to why n does not get to the exact value you set, I'm not sure that is something with python internal that I'm not familiar with, in my case it goes over by 11

Answer 3

The second part of your question "why does the sequence not reach try 1000" is actually a really interesting question, but I'll start with your first question ("why is n decreasing) since it is much simpler to answer.

The value of n decreases because when you reach the maximum recursion limit, your call stack starts to unravel. When a function is done executing, it will return back to whoever called it. Think of it like adding 10 pancakes to your plate, and then eating them from top to bottom one by one. The first one you eat will be the top pancake (the last function call), and the last one you eat will be at the bottom (the first function call, which was f(0)). So n increases as you recursively call the functions, and then decreases it begins to unravel back down to the original caller (ie main).

The reason why it doesn't reach 1000 precisely is a bit more interesting. If I try the below code, we acc get the answer we might except of 999:

def f(n):
    n += 1
    try:
        f(n)
    except RecursionError:
        print(n)
f(0)
>>> 999

The answer is 999 and not 1000 because the stack starts with main already pushed onto it. Now if we add a print statement before we recurse, the answer becomes 996:

def f(n):
    n += 1
    try:
        print(n)
        f(n)
    except RecursionError:
        print(n)
f(0)
>>> 1
>>> 2
>>> ...
>>> 996

I suspect if you look at the underlying implementation of the print statement, it has some additional nested function calls. This means the f(n) call isn't triggering the recursion error, but the print statement is, which is why we get 996 instead of 999 (ie the depth of the print statement would be 3).