Python Recursion

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()