Supongamos que queremos calcular algunos números de Fibonacci, módulo 997.
Para n=500 en C++ podemos ejecutar
#include <iostream> #include <array> std::array<int, 2> fib(unsigned n) { if (!n) return {1, 1}; auto x = fib(n - 1); return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997}; } int main() { std::cout << fib(500)[0]; }y en Python
def fib(n): if n==1: return (1, 2) x=fib(n-1) return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997) if __name__=='__main__': print(fib(500)[0])Ambos encontrarán la respuesta 996 sin problemas. Tomamos módulos para mantener un tamaño de salida razonable y usamos pares para evitar la ramificación exponencial.
Para n=5000 , el código C++ genera 783, pero Python se quejará
RecursionError: maximum recursion depth exceeded in comparisonSi añadimos un par de líneas
import sys def fib(n): if n==1: return (1, 2) x=fib(n-1) return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997) if __name__=='__main__': sys.setrecursionlimit(5000) print(fib(5000)[0])entonces Python también dará la respuesta correcta.
Para n=50000 , C ++ encuentra la respuesta 151 en milisegundos mientras Python falla (al menos en mi máquina).
¿Por qué las llamadas recursivas son mucho más baratas en C++? ¿Podemos modificar de alguna manera el compilador de Python para que sea más receptivo a la recursividad?
Por supuesto, una solución es reemplazar la recursividad con la iteración. Para los números de Fibonacci, esto es fácil de hacer. Sin embargo, esto cambiará las condiciones inicial y terminal, y la última es engañosa para muchos problemas (p. ej., poda alfa-beta). Por lo general, esto requerirá mucho trabajo por parte del programador.
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 ciclo 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])