+- Sick Gaming (https://www.sickgaming.net)
+-- Forum: Programming (https://www.sickgaming.net/forum-76.html)
+--- Forum: Python (https://www.sickgaming.net/forum-83.html)
+--- Thread: [Tut] Maximum Recursion Depth in Python (/thread-99408.html)
[Tut] Maximum Recursion Depth in Python - xSicKxBot - 05-17-2022
Maximum Recursion Depth in Python
<div><div class="kk-star-ratings kksr-valign-top kksr-align-left " data-payload="{"align":"left","id":"360156","slug":"default","valign":"top","reference":"auto","count":"0","readonly":"","score":"0","best":"5","gap":"5","greet":"Rate this post","legend":"0\/5 - (0 votes)","size":"24","width":"0","_legend":"{score}\/{best} - ({count} {votes})"}">
<div class="kksr-stars">
<div class="kksr-stars-inactive">
<div class="kksr-star" data-star="1" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="2" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="3" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="4" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" data-star="5" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
</p></div>
<div class="kksr-stars-active" style="width: 0px;">
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
<div class="kksr-star" style="padding-right: 5px">
<div class="kksr-icon" style="width: 24px; height: 24px;"></div>
</p></div>
</p></div>
</div>
<div class="kksr-legend"> <span class="kksr-muted">Rate this post</span> </div>
</div>
<h2><strong>What i</strong>s<strong> Recursion?</strong></h2>
<p>Recursion in programming is a problem-solving concept. </p>
<p>In recursion, a function finds the solution by calling itself once or many times. This function call can be explicit or implicit. </p>
<p class="has-global-color-8-background-color has-background"><img src="https://s.w.org/images/core/emoji/13.1.0/72x72/1f4a1.png" alt="?" class="wp-smiley" style="height: 1em; max-height: 1em;" /><strong>Info</strong>: Recursion, according to (Tang 2013), is when a function or algorithm calls itself one or more times. These calls occur until the program meets a specified condition. When met, processing of repeated calls from the last one called to the first happens.</p>
<p>See below an example of a <a href="https://blog.finxter.com/a-simple-python-factorial-program-using-recursion/" data-type="post" data-id="3678" target="_blank" rel="noreferrer noopener">recursive factorial function</a>.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="12" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">def factorial(n): """ Calculate n! Args: n(int): factorial to be computed Returns: n! """ if n == 0: return 1 return n * factorial(n-1) print(factorial(3))
# 6
</pre>
<p>In the highlighted line in the above snippet the factorial function calls itself. This function calls itself again and again. </p>
<p>This continues until the condition on line 10 is fulfilled. </p>
<p>Then, the previous function calls are evaluated up to the initial call. The condition <code>n == 0</code> is a<em> base case.</em> </p>
<p class="has-global-color-8-background-color has-background"><img src="https://s.w.org/images/core/emoji/13.1.0/72x72/1f4a1.png" alt="?" class="wp-smiley" style="height: 1em; max-height: 1em;" /> <strong>Info</strong>: A <em>base case</em> is very important in a recursive function since it defines the end of the recursive calls. If there exists a faulty <em>base case </em>or a non-existent one in a recursive function, the function calls would go on indefinitely, akin to an infinite while loop. </p>
<p>Recursion utilizes stacks in function calls. Hence, indefinite function calls lead to a <a rel="noreferrer noopener" href="https://blog.finxter.com/c-developer-income-and-opportunity-2/" data-type="post" data-id="204465" target="_blank">C (programming language)</a> stack overflow. This stack overflow, in turn, crashes Python. A size limit introduced to the python interpreter stack prevents potential stack overflow. </p>
<p><strong>See also</strong>: <a rel="noreferrer noopener" href="https://docs.python.org/3/library/sys.html" data-type="URL" data-id="https://docs.python.org/3/library/sys.html" target="_blank">sys — System-Specific Parameters and Functions</a> and below for the call stack in the global frame when the last line evaluates.</p>
<p>You can try it yourself in the memory visualizer:</p>
<p> <iframe loading="lazy" src="https://pythontutor.com/iframe-embed.html#code=def%20factorial%28n%29%3A%0A%20%20%20%20%22%22%22%0A%20%20%20%20Calculate%20n!%0A%0A%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20n%28int%29%3A%20factorial%20to%20be%20computed%0A%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20n!%0A%20%20%20%20%22%22%22%0A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%20%20%23%20by%20definition%20of%200!%0A%20%20%20%20return%20n%20*%20factorial%28n-1%29%0A%20%20%20%20%0Afactorial%283%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false" width="800" height="500" frameborder="0"> </iframe> </p>
<p>Or you just have a look at the screenshots taken from my execution flow:</p>
</p>
<div class="wp-block-image">
<figure class="aligncenter size-full"><img loading="lazy" width="751" height="450" src="https://blog.finxter.com/wp-content/uploads/2022/05/image-150.png" alt="" class="wp-image-360179" srcset="https://blog.finxter.com/wp-content/uploads/2022/05/image-150.png 751w, https://blog.finxter.com/wp-content/uploads/2022/05/image-150-300x180.png 300w" sizes="(max-width: 751px) 100vw, 751px" /></figure>
</div>
<p>A stack frame from a recursive call is a data structure. It contains the variable of a function call parameters at the specific function call. It holds the state of the recursive function at an instance, with specific arguments. </p>
<p>As highlighted below, the return value of each successive call changes according to the argument passed into the recursive call. </p>
<p>When the argument is 0 the return value is 1. When the argument is 1 the return value is 1, and so on until the initial argument of 3, which has a return value of 6.</p>
<div class="wp-block-image">
<figure class="aligncenter size-full"><img loading="lazy" width="777" height="390" src="https://blog.finxter.com/wp-content/uploads/2022/05/image-151.png" alt="" class="wp-image-360181" srcset="https://blog.finxter.com/wp-content/uploads/2022/05/image-151.png 777w, https://blog.finxter.com/wp-content/uploads/2022/05/image-151-300x151.png 300w, https://blog.finxter.com/wp-content/uploads/2022/05/image-151-768x385.png 768w" sizes="(max-width: 777px) 100vw, 777px" /></figure>
</div>
<h2>Types of Recursions</h2>
<p>There are mainly two types of recursion. These types are <strong>direct</strong> and <strong>indirect recursion</strong>. </p>
<p>For <strong>direct recursion</strong>, the recursive call is explicitly declared (see code snippet below). </p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">def direct_recursion(n): if n == 0: return 0 return direct_recursion(n-1)
direct_recursion(4)</pre>
<p>Yet, in <strong>indirect recursion</strong>, the recursive function calls another function which in turn calls it. </p>
<p>For example, we define a new function named <em>indirect_recursion(n). indirect_recursion(n) </em>calls a function called <em>other_function(3).</em> Inside <em>other_function(n) </em>we call <em>indirect_recursion(n) </em>again.<em> </em></p>
<p>This is a case of indirect recursion.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">def indirect_recursion(n): if n == 0: return 0 return n - other_function(n-1) def other_function(n): if n > 0: n -= 2 return indirect_recursion(n) indirect_recursion(3)
</pre>
<p>Besides the above, there are other types of recursion. </p>
<p>There is also tail recursion and head recursion. </p>
<ul>
<li>Head recursion, refers to when the recursive call is at the beginning of a function. </li>
<li>Tail as the name suggests refers to the scenario where the recursive call is the last line of the function. </li>
</ul>
<p>In the direct recursion snippet above, the last line in the function is a sole recursive call. </p>
<p>This is an example of a tail-recursive function. Hence, tail recursion is a particular example of a direct recursion type. </p>
<p>Note, in our recursive factorial function, the last line contains the recursive call. But, it does not qualify to be tail-recursive. This is because the very last operation in that function is multiplication. </p>
<h3>Tail call optimization</h3>
<p>A tail call is not unique to recursive functions. </p>
<p>It refers to the last action that is finally performed by a function or a procedure. </p>
<p>As explained above, if the final action is recursive then the tail call can is a tail-recursion. </p>
<p>Some programming languages like scheme put in place tail call optimization. Tail call optimization ensures constant stack space usage. In (“Tail Call” 2022), tail call optimization, the call stack receives no more stack frames. </p>
<p>Since most of the current function state is no longer needed, hence replaced by the stack frame of the tail call. </p>
<p>As highlighted in the image <em>illustration of a stack frame in the context of a recursive function.</em> Instead of each call generating a new stack frame. This is achieved by modifying the current frame to align with the current argument. This is a powerful technique that allows for the conservation of memory. </p>
<p>Hence, preventing stack overflow in cases of tail recursion functions. As highlighted in this answer (Cronin 2008). The amount of space required for a recursive factorial function is constant for any value argument.</p>
<h3>Tail Call Optimization in Python</h3>
<p>By design, python, unlike languages like scheme, does not support tail call optimization. </p>
<p>This is true for all tail calls, including tail-recursive calls. The main reason for this is python’s emphasis on having complete debug information. This debug information relies on stack traces. </p>
<p>We lose debug info in discarded stacks by implementing tail call optimization. This renders stack trace useless. </p>
<p>Currently, Python, by default, allows for 1000 recursion calls. After exceeding these calls, Python raises a<strong><em> RecursionError: maximum recursion depth exceeded.</em></strong></p>
<h2>How to Get the Current Recursion Limit in Your System in Python?</h2>
<p>The code listing below shows how to find out the current recursion limit in your system.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">import sys
print(sys.getrecursionlimit())</pre>
<p>The default is usually 1000 but it depends on the set-up one is running. </p>
<p>In my current set-up using Anaconda, the recursion limit is 3000. </p>
<p>Recursion limit refers to the number of function calls python allows when recursing.</p>
<h2>How to Set the Recursion Limit in Python?</h2>
<p>It is possible to change the recursion limit. By adding the following code we get rid of <strong><em>RecursionError </em></strong>if the solution lies within the set limit.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="python" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">sys.setrecursionlimit(3500)</pre>
<p>It is important to note that increasing the recursion limit does not change the C-stack size. </p>
<p>Hence, even with increasing the limit stack overflow might still occur since the limit is a safety measure to prevent stack overflow. </p>
<p>The better option might be refactoring the solution. For example, using an iterative solution using loops, and other built-in Python sequences.</p>
<h2>References</h2>
<ul>
<li>Cronin, Kyle. 2008. “Answer to ‘What Is Tail Call Optimization?’” <em>Stack Overflow</em>. https://stackoverflow.com/a/310980.</li>
<li>“Sys — System-Specific Parameters and Functions — Python 3.10.4 Documentation.” n.d. Accessed April 26, 2022. https://docs.python.org/3/library/sys.html#sys.setrecursionlimit.</li>
<li>“Tail Call.” 2022. In <em>Wikipedia</em>. https://en.wikipedia.org/w/index.php?title=Tail_call&oldid=1082917459.</li>
<li>Tang, Daisy. 2013. “CS240: Data Structures & Algorithms I.” March 2013. https://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm.</li>
</ul>
</div>
https://www.sickgaming.net/blog/2022/05/12/maximum-recursion-depth-in-python/