What is the maximum recursion depth in Python and how to increase it

Question

I have this tail recursive function here   def recursive function n  sum       if n  lt  1          return sum     else          return recursive function n-1  sum n   c   998 print recursive function c  0     It works up to n 997  then it just breaks and spits out a RecursionError  maximum recursion depth exceeded in comparison  Is this just a stack overflow  Is there a way to get around it

User · Answer

Use generators   def fib        a  b   0  1     while True          yield a         a  b   b  a   b  fibs   fib    seems to be the only way to get the following line to work is to               assign the infinite generator to a variable  f    fibs next   for x in xrange 1001    for num in f          print num   above fib   function adapted from  http   intermediatepythonista com python-generators

User · Answer

It is a guard against a stack overflow  yes  Python  or rather  the CPython implementation  doesn t optimize tail recursion  and unbridled recursion causes stack overflows  You can check the recursion limit with sys getrecursionlimit  import sys print sys getrecursionlimit     and change the recursion limit with sys setrecursionlimit  sys setrecursionlimit 1500   but doing so is dangerous -- the standard limit is a little conservative  but Python stackframes can be quite big  Python isn t a functional language and tail recursion is not a particularly efficient technique  Rewriting the algorithm iteratively  if possible  is generally a better idea

User · Answer

resource setrlimit must also be used to increase the stack size and prevent segfault The Linux kernel limits the stack of processes  Python stores local variables on the stack of the interpreter  and so recursion takes up stack space of the interpreter  If the Python interpreter tries to go over the stack limit  the Linux kernel makes it segmentation fault  The stack limit size is controlled with the getrlimit and setrlimit system calls  Python offers access to those system calls through the resource module  sys setrecursionlimit mentioned e g  at https   stackoverflow com a 3323013 895245 only increases the limit that the Python interpreter self imposes on its own stack size  but it does not touch the limit imposed by the Linux kernel on the Python process  Example program  main py import resource import sys  print resource getrlimit resource RLIMIT STACK  print sys getrecursionlimit   print    Will segfault without this line  resource setrlimit resource RLIMIT STACK   0x10000000  resource RLIM INFINITY   sys setrecursionlimit 0x100000   def f i       print i     sys stdout flush       f i   1  f 0   Of course  if you keep increasing setrlimit  your RAM will eventually run out  which will either slow your computer to a halt due to swap madness  or kill Python via the OOM Killer  From bash  you can see and set the stack limit  in kb  with  ulimit -s ulimit -s 10000  The default value for me is 8Mb  See also   Setting stacksize in a python script What is the hard recursion limit for Linux  Mac and Windows   Tested on Ubuntu 16 10  Python 2 7 12

User · Answer

If you want to get only few Fibonacci numbers  you can use matrix method   from numpy import matrix  def fib n       return  matrix  0 1  1 1   dtype  object      n  item 1    It s fast as numpy uses fast exponentiation algorithm  You get answer in O log n   And it s better than Binet s formula because it uses only integers  But if you want all Fibonacci numbers up to n  then it s better to do it by memorisation

User · Answer

I realize this is an old question but for those reading  I would recommend against using recursion for problems such as this - lists are much faster and avoid recursion entirely   I would implement this as   def fibonacci n       f    0 1 1      for i in xrange 3 n           f append f i-1    f i-2       return  The   0fth fibonacci number is    0f     n f -1      Use n 1 in xrange if you start counting your fibonacci sequence from 0 instead of 1

User · Answer

We can do that using  lru cache decorator and setrecursionlimit   method  import sys from functools import lru cache  sys setrecursionlimit 15000     lru cache 128  def fib n  int  - gt  int      if n    0          return 0     if n    1          return 1      return fib n - 2    fib n - 1    print fib 14000    Output 3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125  Source functools lru cache

User · Answer

I had a similar issue with the error  Max recursion depth exceeded   I discovered the error was being triggered by a corrupt file in the directory I was looping over with os walk  If you have trouble solving this issue and you are working with file paths  be sure to narrow it down  as it might be a corrupt file

User · Answer

It s to avoid a stack overflow  The Python interpreter limits the depths of recursion to help you avoid infinite recursions  resulting in stack overflows  Try increasing the recursion limit  sys setrecursionlimit  or re-writing your code without recursion  From the Python documentation   sys getrecursionlimit   Return the current value of the recursion limit  the maximum depth of the Python interpreter stack  This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python  It can be set by setrecursionlimit

User · Answer

As  alex suggested  you could use a generator function to do this sequentially instead of recursively    Here s the equivalent of the code in your question   def fib n       def fibseq n               Iteratively return the first n Fibonacci numbers  starting from 0              a  b   0  1         for   in xrange n               yield a             a  b   b  a   b      return sum v for v in fibseq n    print format fib 100000     d      - gt  no recursion depth error

User · Answer

Looks like you just need to set a higher recursion depth   import sys sys setrecursionlimit 1500

User · Answer

Use a language that guarantees tail-call optimisation  Or use iteration  Alternatively  get cute with decorators

User · Answer

import sys sys setrecursionlimit 1500   def fib n  sum       if n  lt  1          return sum     else          return fib n-1  sum n   c   998 print fib c  0

User · Answer

Of course Fibonacci numbers can be computed in O n  by applying the Binet formula  from math import floor  sqrt  def fib n                                                            return int floor   1 sqrt 5    n- 1-sqrt 5    n   2  n sqrt 5   0 5    As the commenters note it s not O 1  but O n  because of 2  n  Also a difference is that you only get one value  while with recursion you get all values of Fibonacci n  up to that value

User · Answer

Many recommend that increasing recursion limit is a good solution however it is not because there will be always limit  Instead use an iterative solution    def fib n       a b   1 1     for i in range n-1           a b   b a b     return a print fib 5

User · Answer

I wanted to give you an example for using memoization to compute Fibonacci as this will allow you to compute significantly larger numbers using recursion   cache      def fib dp n       if n in cache          return cache n      if n    0  return 0     elif n    1  return 1     else          value   fib dp n-1    fib dp n-2      cache n    value     return value  print fib dp 998     This is still recursive  but uses a simple hashtable that allows the reuse of previously calculated Fibonacci numbers instead of doing them again

User · Answer

I m not sure I m repeating someone but some time ago some good soul wrote Y-operator for recursively called function like  def tail recursive func     y operator    lambda f   lambda y  y y   lambda x  f lambda  args  lambda  x x   args     func    def wrap func tail  args       out   y operator  args      while callable out   out   out       return out   return wrap func tail  and then recursive function needs form  def my recursive func g     def wrapped some arg  acc       if  lt condition gt   return acc     return g some arg  acc    return wrapped    and finally you call it in code   tail recursive my recursive func   some arg  acc   for Fibonacci numbers your function looks like this  def fib g     def wrapped n 1  n 2  n       if n    0  return n 1     return g n 2  n 1   n 2  n-1    return wrapped  print  tail recursive fib   0  1  1000000    output    684684301719893411568996526838242546875   actually tones of digits

User · Answer

We could also use a variation of dynamic programming bottom up approach  def fib bottom up n        bottom up    None     n 1      bottom up 0    1     bottom up 1    1      for i in range 2  n 1           bottom up i    bottom up i-1    bottom up i-2       return bottom up n   print fib bottom up 20000

User · Answer

If you often need to change the recursion limit  e g  while solving programming puzzles  you can define a simple context manager like this   import sys  class recursionlimit      def   init   self  limit           self limit   limit         self old limit   sys getrecursionlimit        def   enter   self           sys setrecursionlimit self limit       def   exit   self  type  value  tb           sys setrecursionlimit self old limit    Then to call a function with a custom limit you can do   with recursionlimit 1500       print fib 1000  0     On exit from the body of the with statement the recursion limit will be restored to the default value

[python] What is the maximum recursion depth in Python, and how to increase it?

Examples related to python

Examples related to recursion