Double-Duty Recursive Functions in Python

Functional programming encourages the use of recursive functions in order to tackle bigger problems, allowing you to avoid mutable state and express the problem as small problems. One of the most popular example of recursive functions is the factorial function, which can be written in python as follows:

def factorial(num):
    """
    num must be an integer greater than 0
    """
    if num == 1:
        return num
    else:
        return num * factorial(num - 1)

That’s the old-school approach to recursive functions and an effective enough function for typical usage. But the biggest problem with typical old-school recursive functions is the stack buildup. If the input is too large, a recursive function will cause a stack overflow.

Tail Call Optimization

That’s why there’s such a thing as Tail Recursion, which uses Tail Call Optimization (TCO) in order to make recursive calls run iteratively, avoiding a large stack. I’m not going to dig into TCO much, but I can tell you that most (if not all) Python implementations do not support TCO. But there are easy-to-use workarounds out there, such as this. There are several solutions out there, so check them out and figure out what works best for you.

Another thing I have to tell you about Tail Recursion is that, in order to make your recursive functions able to be optimized via TCO, you need the final value or the next function call to be the last thing done in your function.

If you look at the first example, the first return is fine; it returns the final value. But the second return fails this test. The last thing it does is the multiplication of num and the recursive factorial call.

So how can we make this tail-callable? The usual way is with an accumulator parameter that keeps track of the current value as you make your calls. For example:

def tr_factorial(num, acc):
    """
    num must be an integer greater than 0
    acc should be 1 to do a typical factorial.
    """
    if num == 1:
        return acc
    else:
        return tr_factorial(num - 1, acc * num)

The accumulator, acc, keeps track of the current value as it goes. When making the call, you pass in 1 for acc, and everything works out fine. But who wants to always have to pass in a 1 every time you call the factorial function?

Skipping the Accumulator

If you’re an avid Pythonista, you’ll probably see as simple answer to this problem, but first let me show you what you would normally have to do in this situation with most other languages (specifically ones without default parameters – hint hint).

Normally, you’d have to make an intermediary function, like this:

def factorial_wrapper(num):
    """
    num must be an integer greater than 0
    """
    return tr_factorial(num, 1)

Or, with Python, you could do this:

part_factorial = partial(tr_factorial, acc=1)

But wait… Now we have two functions in order to do the role of one very simple one. Also, in order to avoid confusion, you’d probably hide the two-parameter version from the users of your module. There has to be a simpler way.

Enter default parameters. I don’t know how I lived without default and keyword parameters before I found Python. Overloading methods was always so tedious for me.

Anyway, the solution to our problem is to add =1 to our tail-recursive function and make a change to the doc that lets your users know to avoid passing in their own values:

def new_factorial(num, acc=1):
    """
    num must be an integer greater than 0
    acc is an accumulator used internally. Leave it alone to do a typical
    factorial
    """
    if num == 1:
        return acc
    else:
        return new_factorial(num - 1, acc * num)

This allows you to have the function serve double-duty as both functions from the “normal” way.

Note

Not all recursive functions that can be optimized with TCO require an accumulator variable. An example of one would be a function that recursively goes through a collection to see if it contains a certain value. It only returns True or False, and only does so if it reaches the value or the end of the collection, so nothing needs to be accumulated along the way.

OMG

I cannot tell you how overjoyed I was to discover this awesome use of default parameters. I was writing up a collection designed to be used recursively and I kept using inner functions to hide them when making recursive functions that required an accumulator. This always led to hard-to-read code, since there was another function definition mixed in with the code for calling it. When I realized I could just use a default parameter, the code got a lot easier to read.