Python hit the recursion limit in Competitive Programming.

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.