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.
genius
LikeLike
Why, thank you. Now I just have to figure out what tail recursion trick I’m going to use.
LikeLike
I have a blog as well, and I think I need to enhance the given information I have on there.
Anyways, I wanted to go with you on your just blog.
LikeLike