I have this tail recursive function here:
def recursive_function(n, sum):
if n < 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?
asked Jul 23, 2010 at 23:04
14
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.
Rob Bednark
24.7k21 gold badges78 silver badges121 bronze badges
answered Jul 23, 2010 at 23:08
Thomas WoutersThomas Wouters
128k23 gold badges146 silver badges122 bronze badges
10
Looks like you just need to set a higher recursion depth:
import sys
sys.setrecursionlimit(1500)
answered Jul 23, 2010 at 23:07
David YoungDavid Young
4,5732 gold badges20 silver badges18 bronze badges
2
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
def __enter__(self):
self.old_limit = sys.getrecursionlimit()
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.
P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.
answered May 1, 2018 at 16:37
Eugene YarmashEugene Yarmash
138k39 gold badges318 silver badges372 bronze badges
2
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().
answered Jul 23, 2010 at 23:08
ScharronScharron
16.9k6 gold badges43 silver badges63 bronze badges
1
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.
answered Jan 28, 2017 at 23:40
3
Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.
answered Jul 23, 2010 at 23:12
Marcelo CantosMarcelo Cantos
179k38 gold badges324 silver badges363 bronze badges
4
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.)
answered Sep 6, 2013 at 3:17
DanielDaniel
3,2845 gold badges26 silver badges35 bronze badges
6
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.
answered Oct 14, 2014 at 18:14
TylerTyler
1911 silver badge6 bronze badges
3
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.
answered Feb 17, 2018 at 15:57
bebidekbebidek
5743 silver badges8 bronze badges
1
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.
answered Oct 8, 2015 at 6:19
rwstrwst
2,4562 gold badges28 silver badges35 bronze badges
9
RecursionError: maximum recursion depth exceeded in comparison
Solution :
First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.
The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.
import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())
The default in some version of Python is 1000 and in some other it was 1500
You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.
So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.
import sys
sys.setrecursionlimit(3000)
Please follow this link for more information about somethings cause this issue :
answered Mar 17, 2021 at 16:33
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) -> 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
answered Oct 26, 2019 at 15:26
EmmaEmma
27.2k11 gold badges43 silver badges67 bronze badges
2
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') # -> no recursion depth error
answered Jul 12, 2016 at 16:58
martineaumartineau
117k25 gold badges161 silver badges290 bronze badges
Edit: 6 years later I realized my «Use generators» was flippant and didn’t answer the question. My apologies.
I guess my first question would be: do you really need to change the recursion limit? If not, then perhaps my or any of the other answers that don’t deal with changing the recursion limit will apply. Otherwise, as noted, override the recursion limit using sys.getrecursionlimit(n).
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 Introduction to Python Generators.
martineau
117k25 gold badges161 silver badges290 bronze badges
answered Jul 30, 2015 at 18:32
alexalex
2372 silver badges7 bronze badges
3
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)
answered Apr 13, 2016 at 8:56
Harun ERGULHarun ERGUL
5,6125 gold badges54 silver badges62 bronze badges
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.
answered Mar 12, 2019 at 13:59
import sys
sys.setrecursionlimit(1500)
def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)
c = 998
print(fib(c, 0))
eyllanesc
230k18 gold badges147 silver badges218 bronze badges
answered May 7, 2019 at 5:35
1
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))
answered Nov 12, 2019 at 16:32
xariezxariez
5191 gold badge5 silver badges17 bronze badges
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 <condition>: 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)
answered Dec 14, 2020 at 14:33
wiesiu_pwiesiu_p
5406 silver badges6 bronze badges
I have this tail recursive function here:
def recursive_function(n, sum):
if n < 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?
asked Jul 23, 2010 at 23:04
14
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.
Rob Bednark
24.7k21 gold badges78 silver badges121 bronze badges
answered Jul 23, 2010 at 23:08
Thomas WoutersThomas Wouters
128k23 gold badges146 silver badges122 bronze badges
10
Looks like you just need to set a higher recursion depth:
import sys
sys.setrecursionlimit(1500)
answered Jul 23, 2010 at 23:07
David YoungDavid Young
4,5732 gold badges20 silver badges18 bronze badges
2
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
def __enter__(self):
self.old_limit = sys.getrecursionlimit()
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.
P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.
answered May 1, 2018 at 16:37
Eugene YarmashEugene Yarmash
138k39 gold badges318 silver badges372 bronze badges
2
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().
answered Jul 23, 2010 at 23:08
ScharronScharron
16.9k6 gold badges43 silver badges63 bronze badges
1
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.
answered Jan 28, 2017 at 23:40
3
Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.
answered Jul 23, 2010 at 23:12
Marcelo CantosMarcelo Cantos
179k38 gold badges324 silver badges363 bronze badges
4
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.)
answered Sep 6, 2013 at 3:17
DanielDaniel
3,2845 gold badges26 silver badges35 bronze badges
6
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.
answered Oct 14, 2014 at 18:14
TylerTyler
1911 silver badge6 bronze badges
3
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.
answered Feb 17, 2018 at 15:57
bebidekbebidek
5743 silver badges8 bronze badges
1
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.
answered Oct 8, 2015 at 6:19
rwstrwst
2,4562 gold badges28 silver badges35 bronze badges
9
RecursionError: maximum recursion depth exceeded in comparison
Solution :
First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.
The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.
import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())
The default in some version of Python is 1000 and in some other it was 1500
You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.
So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.
import sys
sys.setrecursionlimit(3000)
Please follow this link for more information about somethings cause this issue :
answered Mar 17, 2021 at 16:33
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) -> 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
answered Oct 26, 2019 at 15:26
EmmaEmma
27.2k11 gold badges43 silver badges67 bronze badges
2
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') # -> no recursion depth error
answered Jul 12, 2016 at 16:58
martineaumartineau
117k25 gold badges161 silver badges290 bronze badges
Edit: 6 years later I realized my «Use generators» was flippant and didn’t answer the question. My apologies.
I guess my first question would be: do you really need to change the recursion limit? If not, then perhaps my or any of the other answers that don’t deal with changing the recursion limit will apply. Otherwise, as noted, override the recursion limit using sys.getrecursionlimit(n).
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 Introduction to Python Generators.
martineau
117k25 gold badges161 silver badges290 bronze badges
answered Jul 30, 2015 at 18:32
alexalex
2372 silver badges7 bronze badges
3
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)
answered Apr 13, 2016 at 8:56
Harun ERGULHarun ERGUL
5,6125 gold badges54 silver badges62 bronze badges
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.
answered Mar 12, 2019 at 13:59
import sys
sys.setrecursionlimit(1500)
def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)
c = 998
print(fib(c, 0))
eyllanesc
230k18 gold badges147 silver badges218 bronze badges
answered May 7, 2019 at 5:35
1
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))
answered Nov 12, 2019 at 16:32
xariezxariez
5191 gold badge5 silver badges17 bronze badges
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 <condition>: 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)
answered Dec 14, 2020 at 14:33
wiesiu_pwiesiu_p
5406 silver badges6 bronze badges
I have this tail recursive function here:
def recursive_function(n, sum):
if n < 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?
asked Jul 23, 2010 at 23:04
14
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.
Rob Bednark
24.7k21 gold badges78 silver badges121 bronze badges
answered Jul 23, 2010 at 23:08
Thomas WoutersThomas Wouters
128k23 gold badges146 silver badges122 bronze badges
10
Looks like you just need to set a higher recursion depth:
import sys
sys.setrecursionlimit(1500)
answered Jul 23, 2010 at 23:07
David YoungDavid Young
4,5732 gold badges20 silver badges18 bronze badges
2
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
def __enter__(self):
self.old_limit = sys.getrecursionlimit()
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.
P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.
answered May 1, 2018 at 16:37
Eugene YarmashEugene Yarmash
138k39 gold badges318 silver badges372 bronze badges
2
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().
answered Jul 23, 2010 at 23:08
ScharronScharron
16.9k6 gold badges43 silver badges63 bronze badges
1
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.
answered Jan 28, 2017 at 23:40
3
Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.
answered Jul 23, 2010 at 23:12
Marcelo CantosMarcelo Cantos
179k38 gold badges324 silver badges363 bronze badges
4
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.)
answered Sep 6, 2013 at 3:17
DanielDaniel
3,2845 gold badges26 silver badges35 bronze badges
6
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.
answered Oct 14, 2014 at 18:14
TylerTyler
1911 silver badge6 bronze badges
3
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.
answered Feb 17, 2018 at 15:57
bebidekbebidek
5743 silver badges8 bronze badges
1
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.
answered Oct 8, 2015 at 6:19
rwstrwst
2,4562 gold badges28 silver badges35 bronze badges
9
RecursionError: maximum recursion depth exceeded in comparison
Solution :
First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.
The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.
import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())
The default in some version of Python is 1000 and in some other it was 1500
You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.
So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.
import sys
sys.setrecursionlimit(3000)
Please follow this link for more information about somethings cause this issue :
answered Mar 17, 2021 at 16:33
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) -> 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
answered Oct 26, 2019 at 15:26
EmmaEmma
27.2k11 gold badges43 silver badges67 bronze badges
2
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') # -> no recursion depth error
answered Jul 12, 2016 at 16:58
martineaumartineau
117k25 gold badges161 silver badges290 bronze badges
Edit: 6 years later I realized my «Use generators» was flippant and didn’t answer the question. My apologies.
I guess my first question would be: do you really need to change the recursion limit? If not, then perhaps my or any of the other answers that don’t deal with changing the recursion limit will apply. Otherwise, as noted, override the recursion limit using sys.getrecursionlimit(n).
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 Introduction to Python Generators.
martineau
117k25 gold badges161 silver badges290 bronze badges
answered Jul 30, 2015 at 18:32
alexalex
2372 silver badges7 bronze badges
3
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)
answered Apr 13, 2016 at 8:56
Harun ERGULHarun ERGUL
5,6125 gold badges54 silver badges62 bronze badges
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.
answered Mar 12, 2019 at 13:59
import sys
sys.setrecursionlimit(1500)
def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)
c = 998
print(fib(c, 0))
eyllanesc
230k18 gold badges147 silver badges218 bronze badges
answered May 7, 2019 at 5:35
1
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))
answered Nov 12, 2019 at 16:32
xariezxariez
5191 gold badge5 silver badges17 bronze badges
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 <condition>: 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)
answered Dec 14, 2020 at 14:33
wiesiu_pwiesiu_p
5406 silver badges6 bronze badges
Рассмотрим задачу получения факториала числа. В математике он обозначается «!» и функция факториала описывается так:
- 0! = 1.
- n! = 1 * 2 * … * n, n > 0.
Напишем функцию, вычисляющую факториал числа n.
def fact(n):
factorial = 1
for i in range(2, n + 1):
factorial *= i
return factorial
print(fact(5))
Давайте немного перепишем определение факториала:
- 0! = 1.
- n! = (1 * 2 * … * (n — 1)) *n = (n — 1)! * n
Мы видим, что для вычисления n! нам нужно найти (n - 1)! и умножить результат на n. Таким образом, мы используем функцию для вычисления нового значения функции. Функции, в которых происходит вызов самих этих функций называют рекурсивными.
Давайте напишем рекурсивную функцию для вычисления факториала. При создании рекурсивных функций необходимо:
- Написать, что вернёт функция при начальном значении аргумента.
- Написать правило получения нового значения на основе уже вычисленных на предыдущих шагах.
def fact(n):
if n == 0: # 0! = 1
return 1
return fact(n - 1) * n # n! = (n - 1)! * n
print(fact(5))
Вывод программы:
120
Обратите внимание, что рекурсивный вариант функции выполняет действия, которые описаны правилом вычисления факториала. Такой стиль программирования называется декларативным. Данный подход описывает сам результат. Функции, которые мы писали ранее, основаны на императивном стиле, и отвечают на вопрос о способе получения результата.
Рассмотрим применение рекурсивной функции для вычисления n-го числа последовательности Фибоначчи. Числа Фибоначчи — последовательность чисел, вычисляемых по следующему правилу:
- Первые два числа последовательности равны 1.
- n-ое число Фибоначчи равно сумме двух предыдущих, то есть fib(n) = fib(n — 1) + fib(n — 2).
Программа с рекурсивной функцией вычисления n-го числа Фибоначчи запишется так:
def fib(n):
if n in (0, 1):
return 1
return fib(n - 1) + fib(n - 2)
print(fib(35))
Вывод программы:
14930352
При запуске программы, можно заметить, что вычисление 35-го числа последовательности происходит с небольшой задержкой. Проверим, сколько времени занимают вычисления. Выполним вычисления 10 раз и выведем среднее время вычисления с точностью 1 мс. В тестировании скорости работы кода нам помогает стандартный модуль timeit.
from timeit import timeit
def fib(n):
if n in (0, 1):
return 1
return fib(n - 1) + fib(n - 2)
print(f"Среднее время вычисления: "
f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")
Вывод программы:
Среднее время вычисления: 2.924 с.
Проверим, сколько времени займут те же вычисления у императивной версии функции.
from timeit import timeit
def fib(n):
f_1, f = 1, 1
for i in range(n - 1):
f_1, f = f, f_1 + f
return f
print(f"Среднее время вычисления: "
f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")
Вывод программы:
Среднее время вычисления: 2e-06 с.
Получили результат 2 микросекунды у императивной функции против почти 3 секунд у рекурсивной. В чём же причина?
Проблема рекурсивной функции заключается в том, что внутри неё происходит два вызова самой себя для каждого значения. И так до тех пор, пока не функция не дойдет до начальных значений аргументов (1 и 1). В итоге появляется несколько рекурсивных веток, которые образуют рекурсивное дерево. Покажем его часть на рисунке.
Числа на схеме показывают номер числа Фибоначчи. Цветом показаны числа с одинаковым номером. Из схемы дерева становится понятно, что рекурсивная реализация функции выполняет много одинаковых вычислений. Давайте добавим счётчик количества вызовов нашей рекурсивной функции:
def fib(n):
global count
count += 1
if n in (0, 1):
return 1
return fib(n - 1) + fib(n - 2)
count = 0
print(f"35-ое число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")
Вывод программы:
35-ое число Фибоначчи равно: 14930352. Количество вызовов рекурсивной функции равно: 29860703.
Для ускорения вычислений нужно запоминать уже посчитанные числа последовательности, а затем использовать их при необходимости. Такой подход называют кэшированием или мемоизацией.
Напишем рекурсивную функцию с кэшированием, использовав для сохранения вычисленных значений словарь, в котором ключами будут номера чисел последовательности, а значения — сами числа.
def fib(n):
global count
count += 1
if n not in cash:
cash[n] = fib(n - 1) + fib(n - 2)
return cash[n]
count = 0
cash = {0: 1, 1: 1}
print(f"35-ое число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")
Вывод программы:
35-ое число Фибоначчи равно: 14930352. Количество вызовов рекурсивной функции равно: 69.
За счет кэширования количество вызовов рекурсивной функции существенно сократилось. Проверим скорость работы нашей функции.
from timeit import timeit
def fib(n):
global count
count += 1
if n not in cash:
cash[n] = fib(n - 1) + fib(n - 2)
return cash[n]
count = 0
cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")
Вывод программы:
Среднее время вычисления: 2e-06 с.
Скорость работы также существенно увеличилась. Попробуем вычислить число Фибоначчи с номером 1000:
from timeit import timeit
def fib(n):
if n not in cash:
cash[n] = fib(n - 1) + fib(n - 2)
return cash[n]
cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")
Вывод программы:
RecursionError: maximum recursion depth exceeded
Программа выдала ошибку по превышению глубины рекурсии. В Python по умолчанию максимальный размер глубины рекурсии равен 1000. Для изменения глубины рекурсии для вашей программы нужно вызвать функцию setrecursionlimit() из стандартного модуля sys и передать новое значение для предела глубины.
from timeit import timeit
from sys import setrecursionlimit
def fib(n):
if n not in cash:
cash[n] = fib(n - 1) + fib(n - 2)
return cash[n]
setrecursionlimit(2000)
cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")
Вывод программы:
Среднее время вычисления: 0.000132 с.
Обратите внимание: максимально возможное значение глубины рекурсии зависит от операционной системы. Поэтому бесконечно его увеличивать не получится.
Итак, наша рекурсивная функция с кэшированием стала работать быстро. Однако есть и недостаток: её код стал читаться сложнее. Поручим процесс запоминания промежуточных значений функции интерпретатору. Для этого в Python в стандартном модуле functools есть функция lru_cache. Её следует использовать так, как показано в следующем примере:
from timeit import timeit
from functools import lru_cache
@lru_cache(maxsize=1000)
def fib(n):
if n in (0, 1):
return 1
return fib(n - 1) + fib(n - 2)
print(f"Среднее время вычисления: "
f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")
Вывод программы:
Среднее время вычисления: 2e-06 с.
Благодаря автоматическому кэшированию, наша функция снова приобрела «декларативный» вид и при этом работает быстро.
Ещё по теме
Функция lru_cache в примере используется как декоратор. Подробнее о них можно почитать в этом материале
Сумма чисел от 1 до n
Если бы я хотел узнать сумму чисел от 1 до n, где n — натуральное число, я мог бы посчитать вручную 1 + 2 + 3 + 4 + … + (несколько часов спустя) + n. А можно просто написать цикл for:
n = 0
for i in range (1, n+1):
n += iИли использовать рекурсию:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)У рекурсии есть несколько преимуществ в сравнении с первыми двумя методами. Рекурсия занимает меньше времени, чем выписывание 1 + 2 + 3 на сумму от 1 до 3.
Для recusion(4) рекурсия может работать в обратную сторону:
Вызов функций: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Принимая во внимание, что цикл [for] работает строго вперед: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Иногда рекурсивное решение проще, чем итеративное решение. Это очевидно при реализации обращения связанного списка.
Как и когда происходит рекурсия
Рекурсия появляется когда вызов функции повторно вызывает ту же функцию до завершения первоначального вызова функции. Например, рассмотрим известное математическое выражение x! (т.е. факториал). Факториал определяется для всех неотрицательных целых чисел следующим образом:
Если число равно 0, то будет 1.
В противном случае ответом будет то, что число умножается на факториал на единицу меньше этого числа.
В Python наивная реализация факториала может быть определена как функция следующим образом:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)Иногда функции рекурсии трудно понять, поэтому давайте рассмотрим поэтапно.
Рассмотрим выражение factorial(3). Эта и все остальные вызовы функций создают
новую
среду. Среда представляет собой таблицу, которая сопоставляет идентификаторы (например, n, factorial, print и т.д.) с их соответствующими значениями.
В любой момент времени вы можете получить доступ к текущей среде с помощью locals(). В первом вызове функции единственная локальная переменная, которая определяется n = 3.Поэтому locals() будет показывать {"n": 3}. Так как n == 3, возвращаемое значение становится n * factorial(n - 1).
На следующем этапе ситуация может немного запутаться. Глядя на наше новое выражение, мы уже знаем, что такое n. Однако мы еще не знаем, что такое factorial(n - 1).
Во-первых, n - 1 принимает значение 2.Затем 2 передаётся factorial как значение для n. Поскольку это новый вызов функции, создаётся вторая среда для хранения нового n.
Пусть A — первое окружение, а B — второе окружение. A всё ещё существует и равен {"n": 3} , однако B (что равно {"n": 2}) является текущей средой. Если посмотреть на тело функции, возвращаемое значение, опять же, n * factorial(n - 1).
Не определяя это выражение, заменим его на исходное выражение return. Делая это, мы мысленно отбрасываем B, поэтому не забудьте заменить n соответственно (т.е. ссылки на B n заменены на n - 1) который использует A n ). Теперь исходное обратное выражение становится n * ((n - 1) * factorial((n - 1) - 1)). Подумайте, почему так?
Теперь давайте определим factorial((n - 1) - 1)). Так как A n == 3, мы пропускаем 1 через factorial. Поэтому мы создаем новую среду C, которая равна {"n": 1}. Мы снова возвращаем значение n * factorial(n - 1). Итак, заменим исходный factorial((n - 1) - 1)) выражения return аналогично тому, как раньше мы скорректировали исходное выражение return. Исходное выражение теперь n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))).
Почти закончили. Теперь нам нужно оценить factorial((n - 2) - 1). На этот раз мы пропустим через 0. Следовательно, должно получиться 1.
Теперь давайте проведём нашу последнюю замену. Исходное выражение return теперь n * ((n - 1) * ((n - 2) * 1)). Напомню, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 - 1) * ((3 - 2) * 1)). Здесь получается 6.
Чтобы убедиться, что это правильный ответ, вспомните, что 3! == 3 * 2 * 1 == 6. Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.
Утверждение, if n == 0: return 1, называется базовым случаем. Потому что это не рекурсия. Базовый случай необходим, без него вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, можно записать факториал таким образом:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в подробности, потому что это редкий случай, и его трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
- Если число равно 0, то ответ равен 0.
- Если число равно 1, то ответ равен 1.
В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.
Мы можем определить это следующим образом:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
Я не буду разбирать эту функцию также тщательно, как и с factorial(3), но окончательное значение возврата fib(5) эквивалентно следующему (синтаксически недействительному) выражению:
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)Решением (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) будет 5.
Теперь давайте рассмотрим еще несколько терминов:
Tail call — это просто вызов рекурсивной функции, который является последней операцией и должна быть выполнена перед возвратом значения. Чтобы было понятно, return foo(n - 1) — это хвост вызова, но return foo(n - 1) + 1 не является (поскольку операция сложения будет последней операцией).
Оптимизация хвоста вызова (TCO или tail cost optimization) — это способ автоматического сокращения рекурсии в рекурсивных функциях.
Устранение хвоста вызова (TCE или tail cost elimination) — это сокращение хвостового вызова до выражения, которое может быть оценено без рекурсии. TCE — это тип TCO.
Оптимизация хвоста вызова может пригодиться по нескольким причинам:
Интерпретатор может снизить объём памяти, занятый средами. Поскольку ни у кого нет неограниченной памяти, чрезмерные рекурсивные вызовы функций приведут к переполнению стека.
Интерпретатор может уменьшить количество переключателей кадров стека.
В Python нет TCO по нескольким причинам, поэтому для обхода этого ограничения можно использовать другие методы. Выбор используемого метода зависит от варианта использования. Интуитивно понятно, что factorial и fib можно относительно легко преобразовать в итеративный код следующим образом:
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return aОбычно это самый эффективный способ устранения рекурсии вручную, но для более сложных функций может быть трудно.
Другим полезным инструментом является декодер lru_cache, который можно использовать для уменьшения количества лишних вычислений.
Теперь вы знаете, как избежать рекурсии в Python, но когда её нужно использовать? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как именно сделать. Однако есть редкие случаи, когда можно использовать рекурсию. Рекурсия распространена в Python, когда ожидаемые вводы не вызовут значительного количества вызовов рекурсивных функций.
Если вы интересуетесь рекурсией, стоит изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия намного полезней.
Хотя приведённый выше пример последовательности Фибоначчи, хорошо показывает, как применять определение в python и позже использовать кэш lru, при этом он имеет неэффективное время работы, из-за того, что выполняет 2 рекурсивных вызова. Количество вызовов функции растет экспоненциально до n.
В таком случае лучше использовать линейную рекурсию:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)Но у этого примера есть проблема в возвращении пары числе вместо одного. Это показывает, что не всегда стоит использовать рекурсию.
Исследование дерева с рекурсией
Допустим, у нас есть такое дерево:
root
- A
- AA
- AB
- B
- BA
- BB
- BBAЕсли мы хотим перечислить все имена элементов, мы можем сделать это с помощью простого цикла for. У нас есть функция get_name(), которая возвращает строку с именем узла, функция get_children(), которая возвращает список всех подузлов данного узла в дереве, и функция get_root() для получить корневой узел.
root = get_root(tree)
for node in get_children(root):
print(get_name(node))
for child in get_children(node):
print(get_name(child))
for grand_child in get_children(child):
print(get_name(grand_child))
# Выводит: A, AA, AB, B, BA, BB, BBAЭтот код работает хорошо и быстро, но что если под-узлы получили свои под-узлы? И эти под-узлы могут иметь больше под-узлов … Что если вы не знаете заранее, сколько их будет? Решением этой проблемы будет использование рекурсии.
def list_tree_names(node):
for child in get_children(node):
print(get_name(child))
list_tree_names(node=child)
list_tree_names(node=get_root(tree))
# Выводит: A, AA, AB, B, BA, BB, BBAВозможно, вы не хотите вывести, а вернуть список всех имён узлов. Это можно сделать с помощью передачи прокручиваемого списка в качестве параметра.
def list_tree_names(node, lst=[]):
for child in get_children(node):
lst.append(get_name(child))
list_tree_names(node=child, lst=lst)
return lst
list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']Увеличение максимальной глубины рекурсии
Существует предел глубины возможной рекурсии, который зависит от реализации Python. Когда предел достигнут, возникает исключение RuntimeError:
RuntimeError: Maximum Recursion Depth Exceeded
Пример программы, которая может вызвать такую ошибку:
def cursing(depth):
try:
cursing(depth + 1) # actually, re-cursing
except RuntimeError as RE:
print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!Можно изменить предел глубины рекурсии с помощью
sys.setrecursionlimit(limit)Чтобы проверить текущие параметры лимита, нужно запустить:
sys.getrecursionlimit()Если запустить тот же метод выше с новым пределом, мы получаем
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!В Python 3.5 ошибка стала называться RecursionError, которая является производной от RuntimeError.
Хвостовая рекурсия — как не надо делать
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Вот пример обратного отсчета, написанного с использованием хвостовой рекурсии:
def countdown(n):
if n == 0:
print("Blastoff!")
else:
print(n)
countdown(n-1)Любое вычисление, которое может быть выполнено с использованием итерации, также может быть выполнено с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
def find_max(seq, max_so_far):
if not seq:
return max_so_far
if max_so_far < seq[0]:
return find_max(seq[1:], seq[0])
else:
return find_max(seq[1:], max_so_far)Хвостовую рекурсию лучше не использовать, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. В таких случаях рекурсивное решение использует больше системных ресурсов, чем итеративное.
Оптимизация хвостовой рекурсии с помощью интроспекции стека
По умолчанию рекурсивный стек Python не превышает 1000 кадров. Это ограничение можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.
#!/usr/bin/env python2.4
# Эта программа показыает работу декоратора, который производит оптимизацию хвостового вызова. Он делает это, вызывая исключение, если оно является его прародителем, и перехватывает исключения, чтобы вызвать стек.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
# Эта программа показыает работу декоратора, который производит
# оптимизацию хвостового вызова. Он делает это, вызывая исключение, если
# оно является его прародителем, и перехватывает исключения, чтобы
# подделать оптимизацию хвоста Эта функция не работает, если функция
# декоратора возвращается без хвоста.
def tail_call_optimized(g):
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException as e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return funcЧтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше:
Факториальный пример:
# "calculate a factorial"
@tail_call_optimized
def factorial(n, acc=1):
if n == 0:
return acc
return factorial(n-1, n*acc)
print(factorial(10000))
# печатает очень большое число
# и не достигает лимита рекурсии.
Пример Фибоначчи:
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print(fib(10000))
# также выводит большое число,
# но не доходит до лимита рекурсииЧтобы выйти из рекурсии, нужно ввести команду stopCondition.
Исходная переменная должна быть передана рекурсивной функции, чтобы сохранить её.