Python 0xC00000FD fix without thread

Question

I have a program that needs to do very deep recursion. I increased the recursion limit to 10**6 using sys.setrecursionlimit(10**6). However, the process exited with this error code:

Process finished with exit code -1073741571 (0xC00000FD)

After reading this question, it turns out that recursion limit does not change stack size, so stack overflow happened. The solution on the question was to use threading.stack_size(), however I'm a beginner at Python and so I don't understand how to use threading.

So how to fix 0xC00000FD on main thread?

I have checked multiple times - I don't have an infinite loop, it is just that my recursion is very deep.

Edit 30/10/2021 : many people here recommend to rewrite the code to use iterative (loop) rather than recursive , and so i did that. Now my code works without stack overflow error anymore. But if anyone knows how to increase main thread stack size , feel free to answer here , i'm still curious if there is any way to increase python main thread stack size because it is possible to increase main thread stack size on other language i learned such as java.

Answer 1

I was a bit surprised to find that setting thread stack size worked (on my Linux machine and I think Windows would work also). I wrote a test that recurses with and without a thread, results being:

$ python3 recurse.py
Testing unthreaded
try 10**4
10000
try 10**5
Segmentation fault (core dumped)
$ python3 recurse.py threaded
Testing threaded
try 10**4
10000
try 10**5
100000
try 10**6
Exception in thread Thread-3:
...
RecursionError: maximum recursion depth exceeded in comparison

The code creates a class that inherits from threading.Thread. The initializer starts and joins its own thread so just instantiate it and you are off to the races. Stack size control is global to the threading module - puzzling that the threading module isn't itself thread safe - so its set just before starting the code and reset when running.

import threading
import sys

# usage: recurse.py [threaded]

sys.setrecursionlimit(10**6)

class MyRecursionThread(threading.Thread):
    """Start the recursion function in a separate thread and
    wait til complete"""
    
    def __init__(self, depth):
        super().__init__()
        self.orig_stack_size = threading.stack_size()
        threading.stack_size(100000*4096) # guessing here
        self.depth = depth
        self.start()
        self.join()

    def run(self):
        # thread is started so return default. Why isn't this
        # thread safe in the threading module!?!
        threading.stack_size(self.orig_stack_size)
        self.result = the_recursive_function(0, self.depth)

def the_recursive_function(cur, depth):
    if cur < depth:
        return the_recursive_function(cur+1, depth)
    else:
        return cur

# probe depth
try:
    threaded = sys.argv[1] == "threaded"
except IndexError:
    threaded = False
    
print("Testing", "threaded" if threaded else "unthreaded")

for i in range(4, 8):
    print(f"try 10**{i}")
    if threaded:
        result = MyRecursionThread(10**i).result
    else:
        result = the_recursive_function(0, 10**i)
    print(result)

Answer 2

If you end up having to convert your recursive functions to iterative approaches, This decorator/class may help ease the pain (depending on the nature of your recursions).

The decorator converts recursive calls in the function to iterative calls with an internal (unlimited) stack. Its main limitations are that it only supports simple recursions where the self-call is part of the return statement, and it requires a change in the way that return statement is expressed. Also, it will add significant overhead to the function calls which will impact performance.

the usage pattern is as follows:

@iterative                       # decorator to modify the function
def fn(...)                      # existing declaration
    ...                          # and implementation
    if baseCase return x         # no change to the base case
    return fn(...),lambda x: ... # isolate alterations to the recursed
                                 # result in a lambda

For example:

@iterative
def factorial(n):
    if n<2: return 1
    return factorial(n-1),lambda f:f*n

print(factorial(10)) # 3628800
            
print(len(str(factorial(10000)))) # 10000! has 35660 digits              
            

@iterative
def sumSquares(n):
    if n<2: return n
    return sumSquares(n-1),lambda f:f+n**2 
            
print(sumSquares(1000000)) # 333333833333500000 


@iterative
def fibo(n):
    if n<2: return n
    return fibo(n-1),fibo(n-2),lambda n1,n2: n1+n2

print(fibo(10))   # 55
print(fibo(1000)) # will work, ... waiting for output ...

Here is the decorator / class:

from collections import deque    
class iterative:
    def __init__(self,func):
        self.func     = func     # decorated function
        self.stack    = deque()  # [(argCount, function to call)]
        self.nested   = False    # nested call flag
        self.recursed = False    # call wants recursion
        self.results  = []       # result stack

    def __call__(self,*args,**kwargs): # replaces original function
        if self.nested:
            self.recursed = True       # defer recursive call to make 
            return lambda: self.func(*args,**kwargs)
        else:
            self.nested = True
            self.stack.append((0,lambda: self.func(*args,**kwargs))) # top
            while self.stack:
                useArgs,fn = self.stack.pop()      # unstack
                if useArgs:                        # lambda on results
                    args = self.results[-useArgs:]
                    self.results = self.results[:-useArgs]
                    self.results.append(fn(*args))          
                else:
                    self.recursed = False    # recursive call
                    result = fn()
                    if self.recursed:        # more recursion -> stack
                        *calls,final = result
                        self.stack.append((len(calls),final))
                        self.stack.extend([(0,r) for r in reversed(calls)])
                    else:
                        self.results.append(result) # base cond. -> results
            self.nested  = False
            return self.results.pop(-1) # final result (and reset)