Why is python recursion so slow?

Question

So, I was busy in standby mode with recursion, and I noticed that a loop using recursion was much slower than a regular while loop, and I was wondering if anyone knew why. I included the tests I did below:

>>> 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 

However, during the last test, I noticed that if I took out the else , it showed a slight speed improvement, so I wonder if the if statement is the cause of this difference in loop speeds?

Answer 1

You wrote your function as tail recursive. In many imperative and functional languages, this will eliminate the tail exception when the compiler replaces the CALL / RETURN instruction sequence with a simple JUMP, making the process more or less the same as iteration, unlike the usual stack frame allocation, the overhead of recursive function calls . However, Python does not use tail recursion exception, as explained in some of these links:

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

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

As you can see from the links, there are reasons why it does not exist by default, and you can crack it in several ways, but by default Python premiums use functions such as generator functions to create complex instruction sequences compared to recursion.

Answer 2

Recursion is quite expensive compared to iteration (in general), because it requires allocating a new stack frame.