Python

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.

Jacob Zimmerman

Jacob is a certified Java programmer (level 1) and Python enthusiast. He loves to solve large problems with programming and considers himself pretty good at design.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

5 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
jsc42
jsc42
8 years ago

Another alternative is to bypass Tail Call Optimisation completely. Any recursive function can be unwound to not use recursion. Usually, this is not straight forward; but in the cited example, it is trivial – just iterate from 1 to num, cumulatively multiplying the control var onto the accumulator initialised to 1.

Jacob Zimmerman
8 years ago
Reply to  jsc42

Thanks for your input, jsc42, but the point was to follow functional conventions, as pointed out in the first sentence.
I’m well aware that most, if not all, recursive functions can be expressed in loops, but the typical simplicity and readability of recursive functions (once you have your head wrapped around them) and lack of mutability are too good to ignore.
Also, the point wasn’t necessarily to push recursion, but rather to help those who use it to find a nicer, cleaner way to make tail recursive functions.

Erik Colban
Erik Colban
8 years ago

If you are going to introduce double duty functions, you should document them properly. Calling your second argument `acc` suggests an iterative process in which the “desired result” slowly but surely builds up into that argument. A recursive function does not describe a process, but is a static definition. In this case: def new_factorial(n, m=1): ”’ n is a non-negative int m is an int Returns n! * m ”’ … Now it is clear what the function is. Should I be interested in finding 5! * -101, I could call `new_factorial(5, -101)`, but more likely I would be more… Read more »

Jacob Zimmerman
8 years ago
Reply to  Erik Colban

In a way, the desired result does build up into that argument; it’s the accumulation of the result so far. I named it that way because that’s the name I usually see for tail recursive function accumulators. Maybe my documentation isn’t the greatest at explaining the final result, but the intention was for acc to only be used by the function itself, not for finding a factorial times another number. Using the function in that way isn’t clear; `factorial(5, -101)` is confusing compared to `factorial(5) * -101`. The second way ends up with one more multiplication, but that’s trivial, even… Read more »

Erik Colban
Erik Colban
8 years ago

As a user of your code I want to know what the contract is. You show me an argument acc, but tell me that it is not for me to use. That confuses me; if I am not to use it, why are you not hiding it from me? If I, as a user, have to chose between two interfaces, one with one single argument num and a second like the one you are suggesting, I’d chose the first one, because the second argument acc is just noise to me. I don’t care about the fact that you might have… Read more »

Back to top button