title: Why is Python recursion so expensive and what can we do about it?
body: <p>Suppose we want to compute some Fibonacci numbers, modulo 997.</p>
  <p>For <code>n=500</code> in C++ we can run</p>
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;array&gt;
  
  std::array&lt;int, 2&gt; fib(unsigned n) {
      if (!n)
          return {1, 1};
      auto x = fib(n - 1);
      return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
  }
  
  int main() {
      std::cout &lt;&lt; fib(500)[0];
  }
  </code></pre>
  <p>and in Python</p>
  <pre class="lang-py prettyprint-override"><code>def fib(n):
      if n==1:
          return (1, 2)
      x=fib(n-1)
      return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)
  
  if __name__=='__main__':
      print(fib(500)[0])
  </code></pre>
  <p>Both will find the answer 996 without issues. We are taking modulos to keep the output size reasonable and using pairs to avoid exponential branching.</p>
  <p>For <code>n=5000</code>, the C++ code outputs 783, but Python will complain</p>
  <pre class="lang-none prettyprint-override"><code>RecursionError: maximum recursion depth exceeded in comparison
  </code></pre>
  <p>If we add a couple of lines</p>
  <pre class="lang-py prettyprint-override"><code>import sys
  
  def fib(n):
      if n==1:
          return (1, 2)
      x=fib(n-1)
      return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)
  
  if __name__=='__main__':
      sys.setrecursionlimit(5000)
      print(fib(5000)[0])
  </code></pre>
  <p>then Python too will give the right answer.</p>
  <p>For <code>n=50000</code> C++ finds the answer 151 within milliseconds while Python crashes (at least on my machine).</p>
  <p>Why are recursive calls so much cheaper in C++? Can we somehow modify the Python compiler to make it more receptive to recursion?</p>
  <p>Of course, one solution is to replace recursion with iteration. For Fibonacci numbers, this is easy to do. However, this will swap the initial and the terminal conditions, and the latter is tricky for many problems (e.g. alpha–beta pruning). So generally, this will require a lot of hard work on the part of the programmer.</p>