Recursion
(Each of the code snippets in this post is linked to a Scala Worksheets that you can clone and run to follow along. You can also copy code snippets in to Scastie too.)
My name is Brad Carter and I’m a software engineer at Axon. Recently, my team has been growing rapidly and we’ve added about a half dozen engineers since the beginning of the year. As I’ve mentioned previously, most of our backend services are written in Scala and a big part of helping onboard new engineers is acting as a guide to the language and to functional programming generally.
Recently, one of my new teammates came to me with some questions about recursion. “I’ve read some articles and watched some videos and I understand that, in addition to many other use cases, recursion can be used to iterate over the elements of a collection in largely the same way that a loop can. My question, though, is ‘Why bother?’ Both loops and recursion are certainly capable of solving this problem, so why is the functional programming community so married to the approach that feels so unintuitive and which has such a high learning curve?”
I’ve been doing functional programming for a couple of years at this point, and I’ve developed some intuition for the benefits at this point (as well as a moderate preference for it), but I wasn’t able to put that intuition into words in that moment. I sputtered something about how “recursion has no moving parts,” but that answer didn’t leave either of us particularly satisified. I had to do some reflection to put my intuition into words.
This post is about what I found out.
Let’s Talk About Side Effects
I don’t know if this is historically accurate, but I sometimes view functional programming as a sort of response to imperative programming. More specifically, I view recursion as a response to some of the rougher edges of how we perform computations in the imperative paradigm. To understand the benefits of recursion, we first need to understand those rough edges.
All programming languages are made up of statements, and imperative languages like C, Java, and Python, are made up of a specific type of statements called an instruction. (If you think back to grammar class, you may remember that the word ‘imperative’ means ‘command’ or ‘instruction’.) Instructions are executed, and when they are executed, they change some aspect of the world around them. These changes are called side effects.
Side effects come in many shapes and varieties. At the macro level, I can use the smart home app on my phone to lock my front door or my banking app to move money between accounts. At a smaller level, I can also use side effects to write a warning to the console or increment a variable within my program.
Computation by Side Effect
If we need to calculate a result in an imperative program, we usually accomplish that with side effects. Specifically, we start by declaring a piece of data and then we repeatedly change, or mutate, the data with side effect after side effect until we’ve hammered it into a shape that agrees with us.
Let’s look at an example. Say that we want to calculate the sum of a list of numbers. We could do that with code like this:
In this example, we’re given a list that we want to sum up and we start by declaring a variable to hold the sum. We then iterate over the elements of the list, adding each element to the current value of total and then overwriting total with the new result. We repeat the process until we’re out of list elements, at which point we write the result to the console.
There are some big advantages to doing calculations in this way. It’s simple to write and easy to understand. On the whole, I find that this technique tends to mirror the approach I would use if I were solving this problem by hand.
There are some disadvantages too though.
Unintended Side Effects
When building software of significant scope or complexity, it’s common to work on a team and to share your codebase with teammates.
What happens if a teammate accidentally mutates some state that I depend on in a way that I didn’t expect? For instance, what if a teammate wanted to sum some other numbers together and accidentally reused the total variable before I was done with it in the previous example? Or what if a non-private field is overwritten on a data object that’s being passed around between five or six modules in the system? Or what if the intern tries to touch that one global variable that that rest of the team know to stay away from? Hopefully, the regression would be caught by a unit test and maybe even prompt a refactor, but that’s not a given. If the mistake isn’t noticed, my result will change and the program could break.
I suspect that a number of you are thinking to yourselves at this point, “But those are hardly fair examples though! Those are all well known code smells and any imperative programmer worth their salt would know to stay away from functions with multiple responsibilities, public data fields, and global variables.”
That’s a fair point, but it’s not entirely by coincidence that I picked these three examples either.
The imperative programming community is full of smart people, many of whom long ago recognized the dangers represented by inadvertent state mutations and who responded with strategies designed to mitigate the danger. In large part, these strategies take the form of the stylistic conventions and guidelines that limit access to mutable state. These conventions are the code smells that we just referenced.
Overall, these strategies have been highly effective at reducing opportunities for inadvertent state mutations, but they not fool proof though. The effectiveness of stylistic conventions is ultimately limited by how dedicated their practitioners are to following them. While I find it rare to see a global variable in a production system, it’s not as uncommon to see public data fields (or at least data fields whose setter method don’t provide any validation) or overly long methods with multiple responsibilities either.
However, there is also a somewhat more aggressive approach to preventing inadvertent state mutations.
Computation by Expression
Earlier, we said that imperative programming is built on a type of statement called an instruction, but instructions aren’t the only type of statements though. Another is the expression, which is the building block of the functional programming paradigm.
Whereas instructions are executed to produce side effects, expressions are evaluated to produce results. For example, the expression 3 + 5 evaluates to the result 8.
One big difference between an expression and an instruction is that expressions don’t modify or consume their inputs. Adding 3 and 5 together produces 8, but it doesn’t change the 3 or 5. They’re still there, and that’s a really big deal, because it means that the inputs (and outputs) of expressions don’t need to be mutable. If we do our computations with expressions instead of instructions, all the intermediate values in our computations can be immutable, and that eliminates the possibility of inadvertent state mutations outright.
That’s huge! But how do we do computations with only expressions though? Let’s look at some examples.
In general, expression take a fixed number of inputs and perform a fixed number of operations to produce a result:
In these two examples, we first take 5 integer inputs and perform 4 addition operations to combine them into a single sum. In the second, we take 3 strings as input and perform up to 3 comparisons of length to find the longest input.
This capability is powerful, but it also seems quite rigid and inflexible. It’s not very common that I need to find the sum of exactly five numbers, and even when it does come up, sumOf5Numbers doesn’t help me sum together four or six numbers either.
Expressions give us the power of immutability, but they also carry the rigid limitations of a fixed number of inputs and operations, and this may seem to be wholly at odds with the idea of doing work on inputs of arbitrary size.
How do we solve that problem? Let’s look at another example from earlier: summing together the elements of a list.
Problems of Unknown Size
The two limitations of an expression are that we get a fixed number of inputs and a fixed number of operations. That first problem is pretty easy to solve if we remember that we can represent an arbitrary number of inputs as a single entity with a collection type like a list:
We now have the signature for our function, but the second part of the problem still seems like a pretty tall order. How do we then sum together the elements of a list of arbitrary size with a fixed number of addition operations?
Let’s see if we can start by breaking that problem into some simpler cases. In fact, let’s start with the easiest case of all, a list with exactly one element. If I have a list with exactly one element, then the sum of all elements in the list will be the sum of the only element in the list, which is just the value of the element itself. Therefore, we can check if our list has exactly one element, and then return the value of that element if that’s the case:
There’s another neighboring case that we should consider here too, which is the list with no elements. There may be some mathematicians out there who aren’t entirely comfortable with the idea that a list with no elements can have a sum at all. However, I’m not a mathematician and I think this result is reasonable for our use case, so I’m going to say that we can also explicitly check for empty lists and return 0 if we find one too:
We’ve now considered a list with one element and it’s neighbor, the list with no elements. Next, we should look at it’s other neighbor: the list with at least one element. This case seems tricky because we’re back in the territory of lists of arbitrary size, but there is some information that we can glean from what we are given.
We know that there is at least one element in the list, so we can retrieve it and give it a name. We also know that there are 0 or more elements following that first element which conceptually make up another list. We can get a hold of them by subtracting or un-prefixing that first element from the initial list:
(This operation of splitting a list into the first element and a list of subsequent elements is so common in functional programming that those two entities have established names: head and tail respectively.)
Finding the sum of head is pretty easy since, as we’ve already established, the sum of a single value is just the value itself. But how do we find the sum of tail though? tail is a list of integers. If I could turn that list of integers into a sum somehow, then I could just add it to head to get the sum of the whole list, but I don’t have any tools to turn a list of integers into a sum do I?
Oh, wait, actually I do!
That’s the whole purpose of the function that I’m currently building! I can use sumElements find the sum of tail:
To compute the sum of a list of arbitrary size, we have to break the input list into a head and tail, compute the sum of the tail using the same summing function that we’re in the process of building, and then combine the sum of the tail with the head to form the sum of the input list. In other words, we have to solve the problem recursively.
Computation by Expression provides us with powerful characteristics like immutability, but to reap the benefits, we have to follow the rules and that means working with a fixed number operations. This is trivial for problem of fixed size like summing together exactly 5 integers. For problems of arbitrary or unknown size though, we have to get a little more creative. Generally, that means breaking a problem into a head and a tail, recursively solving the tail, and then combining that tail result with the head to make a new result. Recursion is the multiplier that allows us to apply a fixed number of operations over a problem of unfixed size. It’s how we solve problems of arbitrary size and scope without a single piece of mutable state.
Cleaning Up
Before signing off, the neater part of my brain needs to point out that our recursive solution still has a couple of rough edges that that we could sand down.
Careful observers may have noticed that our initial case, a list with one element is actually just a degenerate form of our recursive case (since a list of one element is also a list with at least one element whose tail is Nil.) This means that we can remove the line case List(exactly1Element) => exactly1Element with no ill effects.
Doing so means that we’re now just pattern matching on whether the list has 0 elements or not, which is a good indication that pattern matching is probably overkill for our purpose and that we can substitute a conditional operator instead. I think the result is pretty slick:
Wrapping Up
Good job making it to the end of the post! Today we learned about:
Imperative programming, Computation by Side Effect, and the perils of inadvertent state mutations
How using Computation by Expression gives us immutability, which makes those inadvertent state mutations impossible, but also requires that we build each expression out of a fixed number of operations
How recursion is needed to to build expressions that can handle problems of arbitrary or unknown size.
The last thing I want to say is that both instructions and expressions have their place in any program. My banking app wouldn’t be very good if it couldn’t side effect my money between accounts, nor would it be good if it lost track of funds due to inadvertent state mutations either. I hope this post give you the tools you need to feel more confident about picking the right tool for the job.
Happy Scala-ing!
