¿Por qué es tan lenta la recursión en python?

Así que estaba jugando sin hacer nada con la recursión, y me di cuenta de que un bucle que utilizaba la recursión era mucho más lento que el bucle regular while, y me preguntaba si alguien sabía por qué. He incluido las pruebas que hice a continuación:

>>> import timeit >>> setu="""def test(x): x=x-1 if x==0: return x else: test(x) """ >>> setu2=""" x=10 while x>0: x=x-1 """ >>> timeit.timeit(stmt="test(10)",setup=setu,number=100) 0.0006629826315997432 >>> timeit.timeit(stmt=setu2,number=100) 0.0002488750590750044 >>> setu="""def test(x): x=x-1 if x==0: return x test(x) """ >>> timeit.timeit(stmt="test(10)",setup=setu,number=100) 0.0006419437090698921 

Sin embargo, durante la última prueba, noté que si eliminaba la instrucción else , mostraba una leve mejora en la velocidad, entonces me pregunto si la instrucción if es la causa de esta diferencia de velocidad de bucle.

Has escrito tu función para que sea la cola recursiva. En muchos lenguajes imperativos y funcionales, esto provocaría la eliminación de la recursión de la cola, donde el comstackdor reemplaza la secuencia de instrucciones CALL / RETURN con un JUMP simple, haciendo que el proceso sea más o menos lo mismo que la iteración, en oposición a la asignación de cuadros de stack normal sobrecarga de llamadas de función recursiva. Python, sin embargo, no utiliza la eliminación de recursión de cola, como se explica en algunos de estos enlaces:

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

http://metapython.blogspot.com/2010/11/tail-recursion-elimination-in-python.html

Como puede ver en los enlaces, hay razones por las que no existe de manera predeterminada, y puede piratearlo de varias maneras, pero de manera predeterminada, los premios de Python utilizan cosas como las funciones del generador para crear secuencias complicadas de instrucciones, en lugar de recursion

La recursión es bastante costosa en comparación con la iteración (en general) porque requiere la asignación de un nuevo marco de stack.