Recursion: Thinking Recursively

This lesson has one primary goal: to show that the thought process followed in writing the sum function follows a common recursive programming “pattern.” Indeed, when you write recursive functions you’ll generally follow the three-step process shown in this lesson.

I don’t want to make this too formulaic, but the reality is that if you follow these three steps in your thinking, it will make it easier to write recursive functions, especially when you first start.

As I mentioned in the previous lessons, when I sit down to write a recursive function, I think of three things:

• What is the function signature?

• What is the end condition for this algorithm?

• What is the actual algorithm? For example, if I’m processing all of the elements in a List, what does my algorithm do when the function receives a non-empty List?

Let’s take a deep dive into each step in the process to make more sense of these descriptions.

Once I know that I’m going to write a recursive function, the first thing I ask myself is, “What is the signature of this function?”

If you can describe the function verbally, you should find that you know (a) the parameters that will be passed into the function and (b) what the function will return. In fact, if you don’t know these things, you’re probably not ready to write the function yet.

In the sum function the algorithm is to add all of the integers in a given list together to return a single integer result. Therefore, because I know the function takes a list of integers as its input, I can start sketching the function signature like this:

def sum(list: List[Int]) ...

Because the description also tells me that the function returns an Int result, I add the function’s return type:

def sum(list: List[Int]): Int = ???

This is the Scala way to say that “the sum function takes a list of integers and returns an integer result,” which is what I want. In FP, sketching the function signature is often half of the battle, so this is actually a big step.

The next thing I usually think about is, “How will this algorithm end? What is its end condition?”

Because a recursive function like sum keeps calling itself over and over, it’s of the utmost importance that there is an end case. If a recursive algorithm doesn’t have an end condition, it will keep calling itself as fast as possible until either (a) your program crashes with a StackOverflowError, or (b) your computer’s CPU gets extraordinarily hot. Therefore, I offer this tip:

Always have an end condition, and write it as soon as possible.

In the sum algorithm you know that you have a List, and you want to march through the entire List to add up the values of all of its elements. You may not know it at this point in your recursive programming career, but right away this statement is a big hint about the end condition. Because (a) you know that you’re working with a List, (b) you want to operate on the entire List, and (c) a List ends with the Nil element, (d) you can begin to write the end condition case expression like this:

case Nil => ???

To be clear, this end condition is correct because you’re working with a List, and you know that the algorithm will operate on the entire List. Because the Nil element is to a List as a caboose is to a train, you’re guaranteed that it’s always the last element of the List.

Note: If your algorithm will not work on the entire List, the end condition will be different than this.

Now the next question is, “What should this end condition return?”

A key here is that the function signature states that it returns an Int. Therefore, you know that this end condition must return an Int of some sort. But what Int? Because this is a “sum” algorithm, you also know that you don’t want to return anything that will affect the sum. Hmmm … what Int can you return when the Nil element is reached that won’t affect the sum?

The answer is 0.

(More on this shortly.)

Given that answer, I can update the first case condition:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case ???
}

That condition states that if the function receives an empty List — denoted by Nil — the function will return 0.

Now we’re ready for the third step.

I’ll expand more on the point of returning 0 in this algorithm in the coming lessons, but for now it may help to know that there’s a mathematical theory involved in this decision. What’s happening here is that you’re returning something known as an “identity” element for the current data set and algorithm. As a quick demonstration of what I’m talking about, here are a few other identity elements for different data sets and algorithms:

1) Imagine that you want to write a “product” algorithm for a list of integers. What would you return for the end condition in this case? The correct answer is 1. This is because the product involves multiplying all elements of the list, and multiplying any number by 1 gives you the original number, so this doesn’t affect the final result in any way.

2) Imagine that you’re writing a concatenation algorithm for a List[String]. What would you return for the end condition in this case? The correct answer is `, an emptyString` (because once again, it does not affect the final result).

Now that you’ve defined the function signature and the end condition, the final question is, “What is the algorithm at hand?”

When your algorithm will operate on all of the elements in a List and the first case condition handles the “empty list” case, this question becomes, “What should my function do when it receives a non-empty List?”

The answer for a “sum” function is that it should add all of the elements in the list. (Similarly, the answer for a “product” algorithm is that it should multiply all of the list elements.)

At this point I go back to the original statement of the sum algorithm:

“The sum of a list of integers is the sum of the head element, plus the sum of the tail elements.”

Because the first case expression handles the “empty list” case, you know that the second case condition should handle the case of the non-empty list. A common way to write the pattern for this case expression is this:

case head :: tail => ???

This pattern says, “head will be bound to the value of the first element in the List, and tail will contain all of the remaining elements in the List.”

Because my description of the algorithm states that the sum is “the sum of the head element, plus the sum of the tail elements,” I start to write a case expression, starting by adding the head element:

case head :: tail => head + ???

and then I write this code to represent “the sum of the tail elements”:

case head :: tail => head + sum(tail)

That is a Scala/FP recursive way of expressing the thought, “The sum of a list of integers is the sum of the head element, plus the sum of the tail elements.”

(I described that thought process in detail in the previous lessons, so I won’t repeat all of that thought process here.)

Now that we have the function signature, the end condition, and the main algorithm, we have the completed function:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case head :: tail => head + sum(tail)
}

As I noted in the previous lessons, when FP developers work with lists, they often prefer to use the variable name x to refer to a single element and xs to refer to multiple elements, so this function is more commonly written with these variable names:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => x + sum(xs)
}

(But you don’t have to use those names; use whatever is easiest for you to read.)

In practice, the first step — sketching the function signature — is almost always the first step in the process. As I mentioned, it’s hard to write a function if you don’t know what the inputs and output will be.

But the last two steps — defining the end condition, and writing the algorithm — are interchangeable, and even iterative. For instance, if you’re working on a List and you want to do something for every element in the list, you know the end condition will occur when you reach the Nil element. But if you’re not going to operate on the entire list, or if you’re working with something other than a List, it can help to bounce back and forth between the end case and the main algorithm until you come to the solution.

Note that the sum algorithm I’ve shown specifically works on a Scala List, which ends with a Nil element. It will not work with other sequences like Vector, ArrayBuffer, ListBuffer, or other sequences that do not have a Nil value as the last element in the sequence. I discuss the handling of those other sequences later in the book.

When I sit down to write a recursive function, I generally think of three things:

• What is the function signature?

• What is the end condition for this algorithm?

• What is the main algorithm?

To solve the problem I almost always write the function signature first, and after that I usually write the end condition next, though the last two steps can also be an iterative process.

Now that you’ve seen this “general pattern” of writing recursive functions, the next two lessons are exercises that give you a taste of how to use the patterns to write your own recursive functions.

First, I’ll have you write another recursive function to operate on all of the elements in a List, and then you’ll work on a recursive algorithm that operates on only a subset of a List.