Lesson 7. Rules for recursion and pattern matching

After reading lesson 7, you’ll be able to

• Understand the definition of a recursive function
• Learn the rules for writing recursive functions
• Walk through examples of recursive function definitions
• Use basic pattern matching to solve recursive problems

One of the first challenges of writing practical code in a functional language is that because you don’t have state changes, you also don’t have common looping functions that rely on changing state, such as for, while, and until loops. All iteration problems have to be solved through recursion. For many programmers, this is a terrifying thought, as recursion typically brings up memories of headache-inducing problem solving. Thankfully, you can use a few simple rules to make recursion much easier. Additionally, just as Haskell offers partial application to make closures easier to work with, Haskell provides a feature called pattern matching to make recursion much saner to reason about.

take 3 [1,2,3,4]
[1,2,3]

7.1. Recursion

In general, something is recursive if it’s defined in terms of itself. This normally leads to headaches, as programmers often imagine unwinding an infinite loop of a recursive definition. Recursion doesn’t need to induce headaches, and is often a lot more natural than other forms of iteration in programing. Lists are a recursive data structure defined as an empty list, or an element and another list. No headaches or mystical acts of mental gymnastics are required to work with lists. Recursive functions are just functions that use themselves in their own definition. This, legitimately, sounds confusing.

But if you think of recursive functions as defining recursive processes, recursion becomes fairly mundane. Nearly every human activity is a recursive process! Take washing the dishes. If there are no dishes in the sink, you’re done washing, but if there is a dish, you grab it, clean it, and put it on the rack. To continue washing dishes, you repeat until you’re finished.

7.2. Rules for recursion

The trouble with recursion comes when you write down recursive processes. Even in the case of a list or a dishwashing algorithm, writing these from scratch seems much trickier than just being comfortable with what they are. The secret to writing recursive functions is to not think about the recursion! Thinking about recursion too much leads to headaches. The way to solve recursive functions is by following this simple set of rules:

1. Identify the end goal(s).
2. Determine what happens when a goal is reached.
3. List all alternate possibilities.
4. Determine your “rinse and repeat” process.
5. Ensure that each alternative moves you toward your goal.

7.2.1. Rule 1: Identify the end goal(s)

Generally, recursive processes come to an end. What does this end look like? For a list, the end of the process is the empty list; for washing dishes, it’s an empty sink. After you recognize that something is a recursive process, the first step to solving it is figuring out when you know you’re finished. Sometimes there’s more than one goal. A telemarketer might have to call 100 people or make 5 sales before calling it a day. In this case, the goal is either 100 people have been called, or 5 sales have been made.

7.2.2. Rule 2: Determine what happens when a goal is reached

For each goal you establish in rule 1, you need to figure out what the result will be. In the case of washing dishes, the result is that you’re finished washing the dishes. With functions, you need to return a value, so you have to determine what value should be returned at the end state. A typical problem programmers face is trying to think of the goal state in terms of being the end of a long recursive process. This is usually unnecessary and overly complicated. Often the answer is obvious when you ask the question, “What happens if I call my function on the goal state value?” For example, the end state of the Fibonacci sequence is to arrive at 1; by definition, fib 1 = 1. A more mundane example is determining the number of books you have by counting the number on each shelf. The goal state is to have no more shelves to count; the number of books on no shelves is 0.

7.2.3. Rule 3: List all alternate possibilities

If you aren’t at your goal state, what do you have? This sounds like it can be a lot of work, but most of the time you have only one or two alternatives to being in the goal state. If you don’t have an empty list, you have a list with something in it. If the sink isn’t empty, you have a sink with dishes. For the telemarketer making calls, if you still haven’t called 100 people or made 5 sales, you have two possibilities. You can call and make a sale, or call and not make a sale.

7.2.4. Rule 4: Determine your “Rinse and Repeat”

This rule is nearly identical to rule 2, except you have to repeat your process. Don’t overthink or try to unwind the recursion. For a list, you might take the element and look at the tail. For washing dishes, you wash a dish, put it up to dry, and look in the sink again. The telemarketer either makes the call, records the sale, and repeats, or records that the call was made (no sale) and repeats.

7.2.5. Rule 5: Ensure that each alterative moves you toward the goal

This is a big one! For every process you list in rule 4, you need to ask yourself, “Does this move me closer to the goal?” If you keep taking the tail of a list, you’ll get the empty list. If you keep removing dishes from the sink, you’ll have an empty sink. Recording either sales or calls will eventually cause the counts for each to reach their goal. But suppose you want to flip a coin until you get heads. The goal is getting a head: if you get heads, you stop. The alternate is getting tails: if you get tails, you flip again. But flipping again doesn’t ensure that you’ll ever get heads. Statistically, you should arrive there, so in practice this would be fine, but this is a potentially dangerous function to run (imagine if instead of a coin, you used something with a small chance of success).

7.3. Your first recursive function: greatest common divisor

To introduce recursion, you’ll start with one of the oldest numeric algorithms in existence: Euclid’s algorithm. This algorithm is a remarkably simple method for computing the greatest common divisor (GCD) of two numbers. In case you’ve forgotten, the greatest common divisor of two numbers is the largest number that evenly divides them both. For example, the GCD for 20 and 16 is 4, because 4 is the largest number that divides evenly into both 20 and 16. For 10 and 100, the GCD is 10. Euclid outlined the algorithm in his book Elements (written in about 300 BC). Here’s the basic rundown:

1. You start with two numbers, a and b.
2. If you divide a by b and the remainder is 0, clearly b is the GCD.
3. Otherwise, you change the value of a by assigning it the value of b (b becomes the new a). You also change the value of b to be the remainder you obtained in step 2 (the new b is the remainder of the original a divided by the original b).
4. Then repeat until a/b has no remainder.

Let’s work through one example:

1. a = 20, b = 16
2. a/b = 20/16 = 1 remainder 4
3. a = 16, b = 4
4. a/b = 4 remainder 0
5. GCD = b = 4

To implement this algorithm in code, you want to start with the goal condition (rule 1). The goal is to have no remainder for a/b. In code, you use the modulus function to express this idea. In Haskell, your goal is expressed as follows:

a `mod` b == 0

The next question to answer is what do you return when you reach the goal state (rule 2)? If a/b has no remainder, b must divide a evenly; therefore, b is the GCD. This gives you the entire goal behavior:

if a `mod` b == 0
then b ....

Next you need to figure out all the ways that you can move closer to your goal if your goal isn’t met (rule 3). For this problem, there’s only one alternative: the remainder isn’t 0. If the remainder isn’t 0, you repeat the algorithm with b being the new a and the new b being the remainder: a `mod` b (rule 4):

else gcd b (a `mod` b)

Now you can put all of this into your recursive implementation of Euclid’s algorithm, as shown next.

Listing 7.1. myGCD

myGCD a b = if remainder == 0
            then b
            else myGCD b remainder
  where remainder = a `mod` b

Finally, you make sure you’re moving toward your goal (rule 5). Using the remainder, you’re always going to be shrinking your new b; in the worst case (both numbers are prime), you’ll eventually get to 1 for a and b. This confirms that your algorithm must terminate. By following the rules for creating recursive functions, you’ve avoided having to think too much about endlessly spiraling recursion!

In our myGCD example, only two possible things can happen: either the goal is met, or the process is repeated. This fits nicely into an if then else expression. It’s easy to imagine that as you come across more-complicated functions, you might get larger and larger if then else statements or use case. Haskell has an amazing feature called pattern matching that allows you to peek at the values passed as arguments and behave accordingly. As an example, let’s make a function sayAmount that returns “one” for 1, “two” for 2, and for everything else returns a bunch. First, let’s see how to implement this by using case rather than pattern matching in the function definition.

Listing 7.2. sayAmount v.1

sayAmount n = case n of
  1 -> "one"
  2 -> "two"
  n -> "a bunch"

The pattern matching version of this looks like three separate definitions, each for one of the possible arguments.

Listing 7.3. sayAmount v.2

sayAmount 1 = "one"
sayAmount 2 = "two"
sayAmount n = "a bunch"

Pattern matching, just like case, looks at the options in order, so if you’d placed sayAmount n first in your list, calling sayAmount would always return “a bunch”.

The important thing to realize about pattern matching is that it can look only at arguments, but it can’t do any computation on them when matching. For example, with pattern matching, you can’t check to see whether n is less than 0. Even with this restriction, pattern matching is powerful. You can use pattern matching to check whether a list is empty by matching against []:

isEmpty [] = True
isEmpty aList = False

In Haskell, it’s standard practice to use _ as a wildcard for values you don’t use. In isEmpty, you don’t use the aList parameter, so standard practice is to write it as follows:

isEmpty [] = True
isEmpty _ = False

You can do even more-sophisticated pattern matching on lists. A popular convention in Haskell is to use the single x to represent a single value, and the variable xs to represent a list of values (though we’ll frequently ignore this convention for readability). You could define your own version of head as follows:

myHead (x:xs) = x

To better understand what Haskell is doing as far as pattern matching is concerned, take a look at figure 7.1 to see how Haskell views a list argument as a pattern.

Figure 7.1. Visualizing pattern-matching internals for myHead

Like the real version of head in Haskell, you don’t have a way to handle the case of an empty list, which has no head. You can use Haskell’s error function to throw an error in this case.

Listing 7.4. myHead

myHead (x:xs) = x
myHead [] = error "No head for empty list"

Because you want to think of recursion as merely a list of goals and alternative cases, pattern matching becomes valuable in writing recursive code without getting a migraine. The trick is thinking in patterns. Whenever you write recursive functions, you can split up the definitions so that you’re concerned only with the goal state, always defined first, and then all the possible alternatives one at a time. This often leads to shorter function definitions, but even more important, it makes it easier to reason about each step. Pattern matching is a wonderful way to alleviate the pain and symptoms of recursion.

Summary

In this lesson, our objective was to teach you how to reason about writing recursive functions. When you’re inexperienced in writing recursive functions, the problem often can appear much more challenging than it needs to. Here are the general rules for recursion that should help when you get stuck:

1. Identify the end goal(s).
2. Determine what happens when a goal is reached.
3. List all alternate possibilities.
4. Determine your “rinse and repeat” process.
5. Ensure that each alternative moves you toward the goal.

Let’s see if you got this.

Q7.1

The tail function in Haskell returns an error when called on an empty list. Modify myTail so that it does handle the case of an empty list by returning the empty list.

Q7.2

Rewrite myGCD by using pattern matching.