Tail recusive function in Python

    The issue came from my question in stackoverflow. Basically, it was a misplaced question, because the reason why my program would hit the “RuntimeError: maximum recursion depth exceeded” was that I just passed the sorted array by the first scenario to the second scenario. This caused the second one hit the “worse case” and exceed the “maximum recursion depth”. Well… it was embarrassing to admit that I forgot dereferencing the variable…

Anyway, the question concerning recursion in Python has been in my head for a while, even since I started learning Scheme. This time, the kind answer below my question shed lights on how to solve this kind of problem. Then I dug a little deeper and find more about tail recursion in Python.

The following is an example with problematic way to implement a recursive function:

def fac(n):
    return 1 if n < 2 else n * fac(n - 1)

> fac(3000)
> RuntimeError: maximum recursion depth exceeded

The right way to do this is to make a local helper function “tail recursive” with the help from anonymous function.

def fac(n):
    def f(n, acc):
        return acc if n < 2 else lambda: f(n - 1, acc * n)

    t = f(n, 1)
    while callable(t):
        t = t()
    return t

And an even elegant way is to use built-in function “reduce”:

def fac3(n):
    return reduce(lambda x,y:x*y, xrange(1,n))

The latter two could deal with any input number. Tada~

Extended references:

• Origins of Python’s “Functional” Features
• Tail Recursion Elimination
• Tail Recursion Elimination in Python

Besides, studying Standard ML does give me much much more insights into both programming itself and programming in Python. Except the attractive tail recursion, Python has quite a few amazing features of functional programming.  In retrospect, now I appreciate more about what was listed in the “progression path”, and of course, cannot wait to progress to Haskell.

cheers,