CODEWITHSUNDEEP
pythonperformancerecursionpython-2.7
IT Ninja
IT Ninja

Reputation: 6430

Why is recursion in python so slow?

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?

Upvotes: 16

Views: 18420

Answers (2)

acjay
acjay

Reputation: 36511

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.

Upvotes: 28

Anoop Vaidya
Anoop Vaidya

Reputation: 46533

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

Upvotes: 7

Related Questions