Recursive call optimization

Every programmer sooner or later develops his first recursive function (common examples are calculating a factorial or a Fibonacci number). Recursive functions are usually quite easy to understand and implement, however they may lack performance - especially tail-recursive calls (I don't want to get too much in to low-level programming, but if you're really interested there are tons of articles about it).

A tail recursive call occurs when the last instruction in your function is a function call. Something like this:

def tail_rec_func(x):
    if x > 0:
        return tail_rec_func(x-1)
    else:
        return 0

Now this is one useless piece of code, but it will be a good educational example. Here's what you get when you execute it:

   

>>> tail_rec_func(5)
0
>>> tail_rec_func(1000)
(...)
RuntimeError: maximum recursion depth exceeded

Interesting, this code raises a runtime error stating that that our recursion stack is full. Python has a default recursion limit of 1000 ( sys.getrecurionlimit ) which prevents stack overflows (yes, this is even worse than a runtime error), so increasing the limit will not solve our problem. An obvious solution is replacing tail recursion with an iteration (it's always possible), many compilable languages will optimize this function in the mentioned way, but since python is a scripting language it does not make such straightforward moves - you are responsible for optimizing the code yourself.

In our case:

def iter_tail_rec_func(x):
    while 1:
        if x > 0:
            x -= 1
        else:
            return 0

If you frequently implement tail recursive functions, you had better implement a decorator that converts them to iterations or someday you may find your code crashing with a runtime/stack overflow error.

Cheers!

~KR