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
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)
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.
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
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.
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.
|Reference:||Double-Duty Recursive Functions in Python from our WCG partner Jacob Zimmerman at the Programming Ideas With Jake blog.|
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.
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.
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 »
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 »
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 »