UT Martin Competitive Programming Guidebook

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Recursion Depth Limits ======

===== Factorial =====
The [[https://en.wikipedia.org/wiki/Factorial|factorial function]] is a canonical recursive example. Factorial has a convenient recursive definition as //n//! = //n// * (//n// -- 1)! where 0! = 1! = 1.

The following is a standard implementation derived from this definition:
<file python factorial.py>
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(997))
</file>

In the above example //n//=997 was chosen because any larger will cause the system to throw an exception: ''RecursionError: maximum recursion depth exceeded in comparison''.

A trivial modification will reset the system recursion limit.
<file python factorial_deep.py>
import sys

sys.setrecursionlimit(2000)

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(1997))
</file>

Note that //n//=1997 reflects the new maximum recursion depth in this example.

===== Safety =====
Note that the [[https://docs.python.org/3.7/library/sys.html#sys.setrecursionlimit|official Python3 documentation]] describes an implicit danger in this function, with little guidance as to safe use other than a "platform-dependent" limit.((I.e., It is unlikely that this is a good idea in most/all production settings.)) Exceeding this limit will lead to a crash.

UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Page Tools