Learn You a Haskell for Great Good! - Miran Lipovaca [23]
Then we specify that for any natural number other than 0 or 1, the corresponding Fibonacci number is the sum of the previous two Fibonacci numbers. In other words, F(n) = F(n-1) + F(n-2). For example, F(3) is F(2) + F(1), which in turn breaks down as (F(1) + F(0)) + F(1). Because we’ve now come down to nothing but nonrecursively defined Fibonacci numbers, we can safely say that the value of F(3) is 2.
Recursion is important in Haskell because, unlike with imperative languages, you do computations in Haskell by declaring what something is rather than specifying how you compute it. That’s why Haskell isn’t about issuing your computer a sequence of steps to execute, but rather about directly defining what the desired result is, often in a recursive manner.
Maximum Awesome
Let’s take a look at an existing Haskell function and see how we can write the function ourselves if we shift our brains into the “R” gear (for “recursion”).
The maximum function takes a list of things that can be put in order (i.e., instances of the Ord type class) and returns the largest of them. It can be expressed very elegantly using recursion.
Before we discuss a recursive solution, think about how you might implement the maximum function imperatively. You’d probably set up a variable to hold the current maximum value, then you’d loop through every element of the list. If the current element is bigger than the current maximum value, you’d replace the maximum value with that element. The maximum value that remains at the end of the loop would be the final result.
Now let’s see how we’d define it recursively. First, we need to define a base case: We say that the maximum of a singleton list is equal to the only element in it. But what if the list has more than one element? Well, then we check which is bigger: the first element (the head) or the maximum of the rest of the list (the tail). Here’s the code for our recursive maximum' function:
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list!"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
As you can see here, pattern matching is really useful for defining recursive functions. Being able to match and deconstruct values makes it easy to break down the maximum-finding problem into the relevant cases and recursive subproblems.
The first pattern says that if the list is empty, the program should crash. This makes sense, because we just can’t say what the maximum of an empty list is. The second pattern says that if maximum' is passed a singleton list, it should just return that list’s only element.
Our third pattern represents the meat of the recursion. The list is split into a head and a tail. We call the head x and the tail xs. Then, we make use of our old friend, the max function. The max function takes two things and returns whichever of them is larger. If x is larger than the largest element in xs, our function will return x, otherwise it will return the largest element in xs. But how does our maximum' find the largest element in xs? Simple—by calling itself, recursively!
Let’s work through this code with a specific example, just in case you’re having trouble visualizing how maximum' works. If we call maximum' on [2,5,1], the first two patterns don’t match the function call. However, the third pattern does, so the list value is split into 2 and [5,1], and maximum' is called with [5,1].
For this new call to maximum', [5,1] matches the third pattern, and once again the input list is split—this time into 5 and [1]—and maximum' is recursively called on [1]. This is a singleton list, so the newest call now matches one of our base cases and returns 1 as a result.
Now, we go up a level, comparing 5 to 1 with the use of the max function. 1 was the result of our last recursive call. Since 5 is larger, we now know that the maximum of [5,1]