Tengo esta función recursiva de cola aquí:
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))
Funciona hasta n=997, luego simplemente se rompe y escupe a RecursionError: maximum recursion depth exceeded in comparison. ¿Es esto solo un desbordamiento de pila? ¿Hay alguna forma de evitarlo?
Es una protección contra un desbordamiento de pila, sí. Python (o más bien, la implementación de CPython) no optimiza la recursión de cola, y la recursión desenfrenada provoca desbordamientos de pila. Puede verificar el límite de recursión con sys.getrecursionlimity cambiar el límite de recursión con sys.setrecursionlimit, pero hacerlo es peligroso: el límite estándar es un poco conservador, pero los marcos de pila de Python pueden ser bastante grandes.
Python no es un lenguaje funcional y la recursividad de cola no es una técnica particularmente eficiente. Reescribir el algoritmo iterativamente, si es posible, generalmente es una mejor idea.
syscomo en los resourcemódulos: stackoverflow.com/a/16248113/205521
Parece que solo necesita establecer una mayor profundidad de recursión :
import sys
sys.setrecursionlimit(1500)
Es para evitar un desbordamiento de pila. El intérprete de Python limita las profundidades de recursión para ayudarlo a evitar infinitas recursiones, lo que resulta en desbordamientos de pila. Intenta aumentar el límite de recursión ( sys.setrecursionlimit) o reescribe tu código sin recurrencia.
De la documentación de Python :
sys.getrecursionlimit()Devuelve el valor actual del límite de recursión, la profundidad máxima de la pila de intérpretes de Python. Este límite evita que la recursión infinita provoque un desbordamiento de la pila C y la caída de Python. Se puede establecer por
setrecursionlimit().
Si a menudo necesita cambiar el límite de recurrencia (por ejemplo, mientras resuelve acertijos de programación), puede definir un administrador de contexto simple como este:
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)
Luego, para llamar a una función con un límite personalizado, puede hacer:
with recursionlimit(1500):
print(fib(1000, 0))
Al salir del cuerpo de la withdeclaración, el límite de recursión se restaurará al valor predeterminado.
resource . Sin él, obtendrá una falla de segmentación y todo el proceso de Python se bloqueará si es setrecursionlimitdemasiado alto e intente usar el nuevo límite (aproximadamente 8 megabytes de cuadros de pila, que se traduce en ~ 30,000 cuadros de pila con la función simple anterior, en mi portátil).
Utilice un lenguaje que garantice la optimización de las llamadas de cola. O usa la iteración. Alternativamente, ponte lindo con los decoradores .
ulimit -smarcos de pila, sí, es stackoverflow.com/a/50120316
resource.setrlimit también se debe usar para aumentar el tamaño de la pila y evitar la falla predeterminada
El kernel de Linux limita la pila de procesos .
Python almacena variables locales en la pila del intérprete, por lo que la recursión ocupa espacio en la pila del intérprete.
Si el intérprete de Python intenta superar el límite de la pila, el kernel de Linux lo convierte en un error de segmentación.
El tamaño límite de la pila se controla con las getrlimity setrlimitllamadas al sistema.
Python ofrece acceso a esas llamadas del sistema a través del resourcemódulo.
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)
Por supuesto, si sigue aumentando ulimit, su RAM se agotará, lo que ralentizará su computadora debido a la locura del intercambio o matará a Python a través del OOM Killer.
Desde bash, puede ver y establecer el límite de la pila (en kb) con:
ulimit -s
ulimit -s 10000
El valor predeterminado para mí es 8Mb.
Ver también:
Probado en Ubuntu 16.10, Python 2.7.12.
rlimit_stackdespués de las correcciones de Choque de pila puede provocar fallas o problemas relacionados. También vea Red Hat Issue 1463241
Me doy cuenta de que esta es una vieja pregunta, pero para aquellos que leen, recomendaría no usar la recursividad para problemas como este: las listas son mucho más rápidas y evitan la recursión por completo. Implementaría esto como:
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 en xrange si comienza a contar su secuencia de Fibonacci desde 0 en lugar de 1.)
xrangese llama simplemente range, en Python 3.
Por supuesto, los números de Fibonacci se pueden calcular en O (n) aplicando la fórmula de Binet:
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))Como señalan los comentaristas, no es O (1) sino O (n) debido a 2**n. También una diferencia es que solo obtienes un valor, mientras que con la recursividad obtienes todos los valores de Fibonacci(n)hasta ese valor.
ndebido a la imprecisión de coma flotante: la diferencia entre (1+sqrt(5))**ny se (1+sqrt(5))**(n+1)convierte en menos de 1 ulp, por lo que comienza a obtener resultados incorrectos.
(1+sqrt(5))**ny ((1+sqrt(5))**n)+1eso se convierte en menos de 1 ulp! (error tipográfico pequeño) Además, {@} rwst ¡Eso no es O (1)! El cálculo 2**nlleva al menos O (n) tiempo.
2**nes efectivamente O (log (n)) usando Exponentiattion mediante cuadratura .
Tuve un problema similar con el error "Profundidad máxima de recursión excedida" Descubrí que el error estaba siendo desencadenado por un archivo corrupto en el directorio con el que estaba pasando os.walk. Si tiene problemas para resolver este problema y está trabajando con rutas de archivos, asegúrese de reducirlo, ya que podría ser un archivo corrupto.
Si desea obtener solo unos pocos números de Fibonacci, puede usar el método de matriz.
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)Es rápido ya que numpy usa un algoritmo de exponenciación rápida. Obtiene respuesta en O (log n). Y es mejor que la fórmula de Binet porque solo usa números enteros. Pero si desea todos los números de Fibonacci hasta n, entonces es mejor hacerlo memorizando.
¿Usar generadores?
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 numfunción fib () anterior adaptada de: http://intermediatepythonista.com/python-generators
[fibs().next() for ...]cada vez se crearía un nuevo generador.
Como sugirió @alex , podría usar una función de generador para hacer esto secuencialmente en lugar de recursivamente.
Aquí está el equivalente del código en su pregunta:
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 errorMuchos recomiendan que aumentar el límite de recursión sea una buena solución, sin embargo, no lo es porque siempre habrá un límite. En su lugar, use una solución iterativa.
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)Quería darle un ejemplo para usar la memorización para calcular Fibonacci, ya que esto le permitirá calcular números significativamente mayores utilizando la recursividad:
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))Esto todavía es recursivo, pero utiliza una tabla hash simple que permite la reutilización de números de Fibonacci calculados previamente en lugar de volver a hacerlos.
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))Podemos hacerlo usando @lru_cachedecorador y setrecursionlimit()método:
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))3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125
También podríamos usar una variación del enfoque ascendente de programación dinámica
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))
line <n>, in <module>trazas en la pila) y este código toma 2 cuadros de pilan=1(porque el caso base esn < 1, porn=1lo que aún se repite). Y supongo que el límite de recursión no es inclusivo, ya que en "error cuando alcanza 1000" no "error si excede 1000 (1001)".997 + 2es inferior a 1000, por lo998 + 2que no funciona porque llega al límite.recursive_function(997)funciona, se rompe a las998. Cuando lo llamarecursive_function(998), usa 999 marcos de pila y el intérprete agrega 1 marco (porque su código siempre se ejecuta como si fuera parte del módulo de nivel superior), lo que hace que llegue al límite de 1000.