Differences

This shows you the differences between two versions of the page.

--- python3:recursion_depth [2019/05/07 12:52]
jguerin Added a title.
+++ python3:recursion_depth [2019/05/07 13:10] (current)
jguerin Modified footnote to reference "production" rather than "contests."
@@ Line 1: / Line 1: @@
 ====== 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

Differences

Page Tools