Python hit the recursion limit in Competitive Programming.

Jimmy (xiaoke) Shen
3 min readNov 28, 2023

By default the python has a default maximum recursion limitation, which is 1000. We can adjust it a little bit by using the following code:

import sys                                                                              
sys.setrecursionlimit(10000)

Recently, I encountered a problem in a problem from code forces, which by using Python’s recursion way, a recursion error will be hit.

Problem:

C. Anji’s Binary Tree

Error

Code for the problem

# Definition for a binary tree node.
INF = 1 << 30
import sys
sys.setrecursionlimit(300001)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self, vals, edges):
nodes =[TreeNode(val=v) for v in vals]
for i, (u, v) in enumerate(edges):
if u != 0:
nodes[i].left = nodes[u-1]
if v != 0:
nodes[i].right = nodes[v-1]
self.root = nodes[0]
def helper(self, node):
if node is None:
return INF
if node.left is None and node.right is None:
return 0
left = self.helper(node.left)
right = self.helper(node.right)
if node.val == "U":
return min(left, right) + 1
elif node.val == "L":
L , R = left, right + 1
return min(L, R)
else:
L , R = left + 1, right
return min(L, R)




def solve(self):
ret = self.helper(self.root)
print(ret)

def solve():
n = int(input())
vals = input()
edges = []
for i in range(n):
u, v = [int(ele) for ele in input().split()]
edges.append((u, v))
s = Solution(vals, edges)
s.solve()
T = int(input())
for _ in range(T):
solve()

Local code to reproduce the error

You can also use the following code to reproduce the error:

# Definition for a binary tree node.                                                    
import random
INF = 1 << 30
import sys
sys.setrecursionlimit(10000)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self, vals, edges):
nodes =[TreeNode(val=v) for v in vals]
for i, (u, v) in enumerate(edges):
if u != 0:
nodes[i].left = nodes[u-1]
if v != 0:
nodes[i].right = nodes[v-1]
self.root = nodes[0]
self.call = 0
def helper(self, node):
if node is None:
return INF
print(self.call)
self.call += 1
if node.left is None and node.right is None:
return 0
if node.left is None:
return (node.val != 'R') + self.helper(node.right)
if node.right is None:
return (node.val != 'L') + self.helper(node.left)

left = self.helper(node.left)
right = self.helper(node.right)
if node.val == "U":
return min(left, right) + 1
elif node.val == "L":
L , R = left, right + 1
return min(L, R)
else:
L , R = left + 1, right
return min(L, R)




def solve(self):
ret = self.helper(self.root)
print(ret)

def solve():
"""
n = int(input())
vals = input()
edges = []
for i in range(n):
u, v = [int(ele) for ele in input().split()]
edges.append((u, v))
"""
n = 29000
vv = "LRU"
vals = [random.choice(vv) for _ in range(n)]
vals = "".join(vals)
edges = [[0, 0] for _ in range(n)]
for i in range(n-1):
edges[i][1] = i + 2


s = Solution(vals, edges)
s.solve()
solve()

You will get the following error:

Traceback (most recent call last):
File "ttt.py", line 29, in helper
return (node.val != 'R') + self.helper(node.right)
File "ttt.py", line 29, in helper
return (node.val != 'R') + self.helper(node.right)
File "ttt.py", line 29, in helper
return (node.val != 'R') + self.helper(node.right)
[Previous line repeated 996 more times]
File "ttt.py", line 24, in helper
print(self.call)
RecursionError: maximum recursion depth exceeded while calling a Python object

The deep reason

Based on the discussion Python | Handling recursion limit, the root reason is python does not use the tail recursion, which cause the issue.

How to fix

Switch to other language in this scenario

As mentioned here, you can switch to other languages for competitive programming’s purpose, or you can have two languages as Python does have lots of good features.

Use a bottom up way instead of recursion.

--

--