*Written by Bibin Muttappillil.*

Python is not designed to deal with deep recursive function calls. Nevertheless we want to do this at SOI (as some algorithms can be expressed nicely with recursion). So we need some hacks to resolve this problem.

Here is an example that causes problems:

def recursive_function(x): if x <= 0: return recursive_function(x-1) recursive_function(1_000_000)

See Python on the SOI Grader for more remarks regarding Python at SOI.

## Problems

### Problem 1: maximum recursion depth

Python limits the recursion depth by default.
This can be solved by calling `sys.setrecursionlimit(desired_recursion_depth)` from the `sys` module.

### Problem 2: stack size too small

Even with the above fix you might get the next error: `terminated by signal SIGSEGV (Address boundary error)`.
This roughly means that there is not enough space for the stack to store all the local variables for your recursive calls.

On Linux this can be solved by calling ``
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])`` from the `resource` module.

On Windows you need to set the stack size for threads with `threading.stack_size(desired_stack_size)` and run your code in a new thread (see below for a full working sample).

## Solution for Linux (and MacOS?)

import sys import resource sys.setrecursionlimit(1_000_000) resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY]) def recursive_function(x): if x <= 0: return recursive_function(x-1) recursive_function(1_000_000)

## Solution for Windows

import sys import threading def recursive_function(x): if x <= 0: return recursive_function(x-1) def main(): recursive_function(100_000) sys.setrecursionlimit(100_100) threading.stack_size(0x10000000-0x4000) thread = threading.Thread(target=main) thread.start() thread.join()