tips

Python has a limit on recursion depth (around 1000 recursive calls by default)

To increase more set recursion limit higher than the string length (Not good for higher limit)

import sys
sys.setrecursionlimit(60000)  

Use Iterative approach for better result (while loop)