Why is recursion in python so slow?

Question

So I was messing around in idle with recursion, and I noticed that a loop using recursion was much slower then a regular while loop, and I was wondering if anyone knew why. I have included the tests that I had done 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

During the last test however, I noticed that if I took out the else statement, it showed a slight improvement in speed, so I am wondering if the if statement is the cause of this loop speed difference?

Answer 1

You've written your function to be tail recursive. In many imperative and functional languages, this would trigger tail recursion elimination, where the compiler replaces the CALL/RETURN sequence of instructions with a simple JUMP, making the process more or less the same thing as iteration, as opposed to the normal stack frame allocation overhead of recursive function calls. Python, however, does not use tail recursion elimination, 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 it doesn't exist by default, and you can hack it in in a number of ways, but by default, Python prizes using things like generator functions to create complicated sequences of instructions, versus recursion.

Answer 2

Recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame.