Una alternativa a un trampolín es usar reduce . si puede cambiar la función recursiva para que sea recursiva de cola, puede implementarla con reduce, aquí hay una posible implementación.

reduce se implementa internamente de forma iterativa, por lo que puede usar su función recursiva sin explotar la pila.

 def inner_fib(acc, num): # acc is a list of two values return [(acc[0]+acc[1]) % 997, (acc[0]+2*acc[1]) % 997] def fib(n): return reduce(inner_fib, range(2, n+1), # start from 2 since n=1 is covered in the base case [1,2]) # [1,2] is the base case

Puede aumentar el límite de recurrencia usando:

 import sys sys.setrecursionlimit(new_limit)

Pero tenga en cuenta que este límite existe por una razón y que Python puro no está optimizado para la recursividad (y las tareas de computación intensiva en general).

El problema es que Python tiene un límite interno en el número de llamadas a funciones recursivas.

Ese límite es configurable como se muestra en la respuesta de Quentin Coumes . Sin embargo, una cadena de funciones demasiado profunda dará como resultado un desbordamiento de pila. Esta limitación¹ subyacente se aplica tanto a C++ como a Python. Esta limitación también se aplica a todas las llamadas a funciones, no solo a las recursivas.

En general: no debe escribir² algoritmos que tengan un crecimiento de profundidad de recursión con complejidad lineal o peor. La recursión de crecimiento logarítmico suele estar bien. Las funciones recursivas de cola son triviales para reescribir como iteraciones. Otras recursiones se pueden convertir en iteración utilizando estructuras de datos externas (generalmente, una pila dinámica).

Una regla general relacionada es que no debe tener objetos grandes con almacenamiento automático. Esto es específico de C++ ya que Python no tiene el concepto de almacenamiento automático.

¹ La limitación subyacente es el tamaño de la pila de ejecución. El tamaño predeterminado difiere entre los sistemas y las diferentes llamadas a funciones consumen diferentes cantidades de memoria, por lo que el límite no se especifica como una cantidad de llamadas, sino en bytes. Esto también es configurable en algunos sistemas. Por lo general, no recomendaría tocar ese límite debido a problemas de portabilidad.

² Las excepciones a esta regla general son ciertos lenguajes funcionales que garantizan la eliminación de la recurrencia de cola, como Haskell, donde esa regla se puede relajar en caso de recurrencias que se garantiza que se eliminarán. Python no es un lenguaje de este tipo, y la función en cuestión no es recursiva en la cola. Si bien los compiladores de C++ pueden realizar la eliminación como una optimización, no está garantizado y, por lo general, no está optimizado en las compilaciones de depuración. Por lo tanto, la excepción generalmente tampoco se aplica a C++.

Descargo de responsabilidad: La siguiente es mi hipótesis; En realidad, no conozco su razón de ser: el límite de Python es probablemente una función que detecta recurrencias potencialmente infinitas, lo que evita posibles bloqueos de desbordamiento de pila inseguros y sustituye un RecursionError más controlado.

¿Por qué las llamadas recursivas son mucho más baratas en C++?

C++ es un lenguaje compilado. Python se interpreta. (Casi) todo es más barato en C++, excepto la traducción del código fuente a un programa ejecutable.

Permítanme primero responder a sus preguntas directas:

¿Por qué las llamadas recursivas son mucho más baratas en C++?

Porque C ++ no tiene limitación en la profundidad de la llamada recursiva, excepto el tamaño de la pila. Y al ser un lenguaje totalmente compilado, los bucles (incluida la recursividad) son mucho más rápidos en C++ que en Python (la razón por la cual los módulos especiales de Python como numpy/scipy usan directamente rutinas C). Además, la mayoría de las implementaciones de C++ usan una característica especial llamada eliminación de recursión de cola (ver más adelante en esta publicación) y optimizan algunos códigos recursivos en equivalentes iterativos. Esto es bueno aquí, pero no está garantizado por el estándar, por lo que otras compilaciones podrían provocar que un programa se bloquee miserablemente, pero la recursividad de la cola probablemente no esté involucrada aquí.

Si la recursividad es demasiado profunda y agota la pila disponible, invocará el conocido comportamiento indefinido en el que puede pasar cualquier cosa, desde un bloqueo inmediato hasta un programa que da resultados incorrectos (en mi humilde opinión, este último es mucho peor y no se puede detectar... )

¿Podemos modificar de alguna manera el compilador de Python para que sea más receptivo a la recursividad?

No. La implementación de Python explícitamente nunca usa la eliminación de recurrencia de cola. Podría aumentar el límite de recurrencia, pero casi siempre es una mala idea (vea más adelante en esta publicación por qué).

Ahora para la verdadera explicación de la razón subyacente.

La recursividad profunda es malvada, punto final. Nunca debes usarlo. La recursividad es una herramienta útil cuando puede asegurarse de que la profundidad se mantendrá dentro de límites sensatos . Python usa un límite suave para advertir al programador que algo anda mal antes de bloquear el sistema. Por otro lado, la optimización de los compiladores de C y C++ a menudo cambia internamente la recursividad de la cola en un bucle iterativo. Pero confiar en él es muy peligroso porque un ligero cambio podría impedir esa optimización y provocar un bloqueo de la aplicación.

Como se encuentra en esta otra publicación de SO , las implementaciones comunes de Python no implementan esa eliminación de recursión de cola . Por lo tanto, no debe usar la recursividad a una profundidad de 5000, sino usar un algoritmo iterativo.

Como su cálculo subyacente necesitará todos los números de Fibonacci hasta el especificado, no es difícil calcularlos iterativamente. Además, ¡será mucho más eficiente!

Una solución es un trampolín: la función recursiva, en lugar de llamar a otra función, devuelve una función que realiza esa llamada con los argumentos adecuados. Hay un ciclo un nivel más alto que llama a todas esas funciones en un ciclo hasta que tenemos el resultado final. Probablemente no lo estoy explicando muy bien; puede encontrar recursos en línea que hacen un mejor trabajo.

El punto es que esto convierte la recursividad en iteración. No creo que esto sea más rápido, tal vez sea incluso más lento, pero la profundidad de recursión se mantiene baja.

Una implementación podría verse a continuación. Dividí el par x en a y b para mayor claridad. Luego convertí la función recursiva a una versión que realiza un seguimiento de a y b como argumentos, lo que la convierte en recursiva.

 def fib_acc(n, a, b): if n == 1: return (a, b) return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997) def fib(n): x = fib_acc(n, 1, 2) while callable(x): x = x() return x if __name__=='__main__': print(fib(50000)[0])

"Ambos encontrarán la respuesta 996 sin problemas"

Veo al menos un problema: la respuesta debería ser 836 , no 996.

Parece que ambas funciones calculan Fibonacci(2*n) % p , y no Fibonacci(n) % p .

996 es el resultado de Fibonacci(1000) % 997 .

Elija un algoritmo más eficiente

Un algoritmo ineficiente sigue siendo un algoritmo ineficiente, sin importar si está escrito en C++ o Python.

Para calcular números de Fibonacci grandes, existen métodos mucho más rápidos que la recursividad simple con llamadas O(n) (consulte elartículo relacionado).

Para n grande, esta función recursiva de Python O(log n) debería ejecutarse en círculos alrededor de su código C++ anterior:

 from functools import lru_cache @lru_cache(maxsize=None) def fibonacci(n, p): "Calculate Fibonacci(n) modulo p" if n < 3: return [0, 1, 1][n] if n % 2 == 0: m = n // 2 v1 = fibonacci(m - 1, p) v2 = fibonacci(m, p) return (2*v1 + v2) * v2 % p else: m = (n + 1) // 2 v1 = fibonacci(m, p) ** 2 v2 = fibonacci(m - 1, p) ** 2 return (v1 + v2) % p print(fibonacci(500, 997)) #=> 836 print(fibonacci(1000, 997)) #=> 996

¡Pruébelo en línea!

Felizmente calculará fibonacci(10_000_000_000_000_000, 997) .

Es posible agregar el nivel de recurrencia como parámetro, para ver qué tan profundo debe llegar la recurrencia y mostrarlo con sangría. Aquí hay un ejemplo para n=500 :

 # Recursion tree: 500 249 124 61 30 14 6 2 3 1 2 7 4 15 8 31 16 62 125 63 32 250

¡Pruébelo en línea!

Sus ejemplos simplemente se verían como diagonales muy largas:

 500 499 498 ... ... 1

Para los ejecutables de Windows, el tamaño de la pila se especifica en el encabezado del ejecutable. Para la versión Windows de Python 3.7 x64, ese tamaño es 0x1E8480 o exactamente 2.000.000 bytes.

Esa versión falla con

 Process finished with exit code -1073741571 (0xC00000FD)

y si buscamos eso , encontramos que es un desbordamiento de pila.

Lo que podemos ver en la pila (nativa) con un depurador nativo como WinDbg (habilitar la depuración de procesos secundarios) es

 [...] fa 000000e9`6da1b680 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371 fb 000000e9`6da1b740 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e fc 000000e9`6da1b980 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371 fd 000000e9`6da1ba40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e fe 000000e9`6da1bc80 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371 ff 000000e9`6da1bd40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e 2:011> ? 000000e9`6da1bd40 - 000000e9`6da1ba40 Evaluate expression: 768 = 00000000`00000300

Entonces, Python usará 2 marcos de pila por llamada de método y hay una enorme diferencia de 768 bytes en las posiciones de la pila.

Si modifica ese valor dentro del EXE (haga una copia de seguridad) con un editor hexadecimal, digamos 256 MB

puedes ejecutar el siguiente código

 [...] if __name__=='__main__': sys.setrecursionlimit(60000) print(fib(50000)[0])

y dará 151 como respuesta.

En C++, también podemos forzar un desbordamiento de pila, por ejemplo, pasando 500.000 como parámetro. Durante la depuración, obtenemos

 0:000> .exr -1 ExceptionAddress: 00961015 (RecursionCpp!fib+0x00000015) ExceptionCode: c00000fd (Stack overflow) [...] 0:000> k [...] fc 00604f90 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] fd 00604fb0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] fe 00604fd0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] ff 00604ff0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] 0:000> ? 00604ff0 - 00604fd0 Evaluate expression: 32 = 00000020

que es solo 1 marco de pila por llamada de método y solo 32 bytes de diferencia en la pila. Comparado con Python, C++ puede hacer 768/32 = 24 veces más recursiones para el mismo tamaño de pila.

Mi compilador de Microsoft creó el ejecutable con el tamaño de pila predeterminado de 1 MB (compilación de lanzamiento, 32 bits):

La versión de 64 bits tiene una diferencia de pila de 64 bits (también versión de lanzamiento).

Herramientas utilizadas:

• Vista previa de Microsoft WinDbg (gratis)
• Sweetscape 010 Editor (comercial) con la plantilla para archivos PE