Last modified on 9 November 2014, at 16:22

Haskell/Recursion

Recursion plays a central role in Haskell (and computer science and mathematics in general). Recursion is merely a form of repetition, but sometimes it is taught in a confusing or obscure way. It is easy enough to understand as long as you separate the meaning of a recursive function from its behaviour.

Generally speaking, a recursive function has two parts to its definition. A function is recursive when one part of its definition includes the function itself again. There must also be at least one base case that does not call the function being defined stopping (i.e. termination) condition; otherwise, recursive functions could lead to infinite regress (i.e. an infinite loop).


Numeric recursionEdit

The factorial functionEdit

In mathematics, especially combinatorics, there is a function called factorial.[1] It takes a single non-negative integer as an argument, finds all the positive integers less than or equal to "n", and multiplies them all together. For example, the factorial of 6 (denoted as 6!) is 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720. We can use a recursive style to define this in Haskell:

Let's look at the factorials of two adjacent numbers:

Example: Factorials of consecutive numbers

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1

Notice how we've lined things up. You can see here that the 6! includes the 5!. In fact, 6! is just 6 \times 5!. Let's look at another example:

Example: Factorials of consecutive numbers

Factorial of 4 = 4 × 3 × 2 × 1
Factorial of 3 =     3 × 2 × 1
Factorial of 2 =         2 × 1
Factorial of 1 =             1

The factorial of any number is just that number multiplied by the factorial of the number one less than it. There's one exception: if we ask for the factorial of 0, we don't want to multiply 0 by the factorial of -1 (factorial is only for positive numbers). In fact, we just say the factorial of 0 is 1 (we define it to be so. Just take our word for it that this is right.[2]). So, 0 is the base case for the recursion: when we get to 0 we can immediately say that the answer is 1, no recursion needed. We can summarize the definition of the factorial function as follows:

  • The factorial of 0 is 1.
  • The factorial of any other number is that number multiplied by the factorial of the number one less than it.

We can translate this directly into Haskell:

Example: Factorial function

factorial 0 = 1
factorial n = n * factorial (n - 1)

This defines a new function called factorial. The first line says that the factorial of 0 is 1, and the second line says that the factorial of any other number n is equal to n times the factorial of n - 1. Note the parentheses around the n - 1; without them this would have been parsed as (factorial n) - 1; remember that function application (applying a function to a value) takes precedence over anything else when grouping isn't specified otherwise (we say that function application binds more tightly than anything else).

Note

The factorial function above is best defined in a file, but since it is a small function, it is feasible to write it in GHCi as a one-liner. To do this, we need to add braces (that is, { and } ) and a semicolon:

    > let { factorial 0 = 1; factorial n = n * factorial (n - 1) }

Haskell actually uses line separation and other whitespace as a substitute for these separation and grouping characters. Haskell programmers generally prefer the clean look of separate lines and appropriate indentations, but explicit use of semicolons and other markers is fine whenever preferred. Note that if we left out the braces in this let statement, the function would use only last definition, losing the terminating base case and thus leading to infinite recursion.


The example above demonstrate a very simple relationship between factorial of a number, n, and the factorial of a slightly smaller number, n - 1.

Think of a function call as delegation. The instructions for a recursive function delegate a sub-task. It just so happens that the delegate function uses the same instructions as the delegator; it's only the input data that changes. The only really confusing thing about recursive functions is the fact that each function call uses the same parameter names, so it can be tricky to keep track of the many delegations.

Let's look at what happens when you execute factorial 3:

  • 3 isn't 0, so we calculate the factorial of 2
    • 2 isn't 0, so we calculate the factorial of 1
      • 1 isn't 0, so we calculate the factorial of 0
        • 0 is 0, so we return 1.
      • To complete the calculation for factorial 1, we multiply the current number, 1, by the factorial of 0, which is 1, obtaining 1 (1 × 1).
    • To complete the calculation for factorial 2, we multiply the current number, 2, by the factorial of 1, which is 1, obtaining 2 (2 × 1 × 1).
  • To complete the calculation for factorial 3, we multiply the current number, 3, by the factorial of 2, which is 2, obtaining 6 (3 × 2 × 1 × 1).

(Note that we end up with the one appearing twice, since the base case is 0 rather than 1; but that's okay since multiplying by 1 has no effect. We could have designed factorial to stop at 1 if we had wanted to, but it's conventional, and often useful, to have the factorial of 0 defined.)

We can see how the result of the recursive call is calculated first, then combined using multiplication. Of course, you'll rarely need to "unwind" the recursion like this when reading or composing recursive functions. Compilers have to implement the behaviour, but programmers can work at the abstract level.


One more thing to note about the recursive definition of factorial: the order of the two declarations (one for factorial 0 and one for factorial n) is important. Haskell decides which function definition to use by starting at the top and picking the first one that matches. If we had the general case (factorial n) before the 'base case' (factorial 0), then the general n would match anything passed into it – including 0. The compiler would then conclude that factorial 0 equals 0 * factorial (-1), and so on to negative infinity (which is definitely not what we want). So, always list multiple function definitions starting with the most specific and proceeding to the most general.

Exercises
  1. Type the factorial function into a Haskell source file and load it into GHCi.
  2. Try examples like factorial 5 and factorial 1000.[3]
    • What about factorial (-1)? Why does this happen?
  3. The double factorial of a number n is the product of every other number from 1 (or 2) up to n. For example, the double factorial of 8 is 8 × 6 × 4 × 2 = 384, and the double factorial of 7 is 7 × 5 × 3 × 1 = 105. Define a doublefactorial function in Haskell.

Loops, recursion and accumulating parametersEdit

Loops are the bread and butter of imperative languages. They are a way to directly specify a sequence of steps to be executed repeatedly by the program. When using an imperative language, loops are often a more natural way of solving problems that would, in Haskell, be dealt with recursion. For example, an idiomatic way of writing a factorial function in C, a typical imperative language, would be using a for loop, like this:

Example: The factorial function in an imperative language

int factorial(int n) {
  int res = 1;
  for ( ; n > 1; n--)
    res *= n;
  return res;
}

Here, the for loop causes res to be multiplied by n repeatedly. After each repetition, 1 is subtracted from n (that is what n-- does). The repetitions stop when n is no longer greater than 1.

A straightforward translation of such a function to Haskell is not possible, since changing the value of the variables res and n (a destructive update) would not be allowed. However, you can always translate a loop into an equivalent recursive form. The idea is to make each loop variable in need of updating into an argument of a recursive function. For example, here is a recursive "translation" of the above loop into Haskell:

Example: Using recursion to simulate a loop

factorial n = go n 1
    where
    go n res
        | n > 1     = go (n - 1) (res * n)
        | otherwise = res

go is an auxiliary function which actually performs the factorial calculation. It takes an extra argument, res, which is used as an accumulating parameter to build up the final result.

Note

Depending on the languages you are familiar with, you might be concerned about performance problems caused by recursion. As far as Haskell is concerned, you should not be worried. Compilers for Haskell and other functional programming languages include a number of optimisations for recursion, which is not surprising given how often it is needed. Another thing to keep in mind is that Haskell is lazy. That means calculations are only performed once their results are required by other calculations, which helps avoiding some of the performance issues usually associated with recursion. We'll further discuss such issues, and some of the subtleties they involve, in later chapters.


Other recursive functionsEdit

As it turns out, there is nothing particularly special about the factorial function; a great many numeric functions can be defined recursively in a natural way. For example, let's think about multiplication. When you were first introduced to multiplication (remember that moment? :)), it may have been through a process of 'repeated addition'. That is, 5 × 4 is the same as summing four copies of the number 5. Of course, summing four copies of 5 is the same as summing three copies, and then adding one more – that is, 5 × 4 = 5 × 3 + 5. This leads us to a natural recursive definition of multiplication:

Example: Multiplication defined recursively

mult _ 0 = 0                      -- anything times 0 is zero
mult n 1 = n                      -- anything times 1 is itself
mult n m = (mult n (m - 1)) + n   -- recurse: multiply by one less, and add an extra copy

Stepping back a bit, we can see how numeric recursion fits into the general recursive pattern. The base case for numeric recursion usually consists of one or more specific numbers (often 0 or 1) for which the answer can be immediately given. The recursive case computes the result by calling the function recursively with a smaller argument and using the result in some manner to produce the final answer. The 'smaller argument' used is often one less than the current argument, leading to recursion which 'walks down the number line' (like the examples of factorial and mult above). However, the prototypical pattern is not the only possibility; the smaller argument could be produced in some other way as well.

Exercises
  1. Expand out the multiplication 5 × 4 similarly to the expansion we used above for factorial 3.
  2. Define a recursive function power such that power x y raises x to the y power.
  3. You are given a function plusOne x = x + 1. Without using any other (+)s, define a recursive function addition such that addition x y adds x and y together.
  4. (Harder) Implement the function log2, which computes the integer log (base 2) of its argument. That is, log2 computes the exponent of the largest power of 2 which is less than or equal to its argument. For example, log2 16 = 4, log2 11 = 3, and log2 1 = 0. (Small hint: read the last phrase of the paragraph immediately preceding these exercises.)

List-based recursionEdit

A lot of functions in Haskell turn out to be recursive, especially those concerning lists.[4] Let's begin by considering the length function, that finds the length of a list:

Example: The recursive definition of length

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

Let's explain the algorithm in English to clarify how it works. The type signature of length tells us that it takes any type of list and produces an Int. The next line says that the length of an empty list is 0; and that, naturally, is the base case. The final line is the recursive case: if a list isn't empty, then it can be broken down into a first element (here called x) and the rest of the list (which will just be the empty list if there are no more elements) which will be called xs (i.e. plural of x). The length of the list is 1 (accounting for the x) plus the length of xs (as in the tail example in Next steps, xs is set when the argument list matches the (:) pattern).

How about the concatenation function (++), which joins two lists together?

Example: The recursive (++)

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"
(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

This is a little more complicated than length but not too difficult once we break it down. The type says that (++) takes two lists of the same type and produces another list of the same type. The base case says that concatenating the empty list with a list ys is the same as ys itself. Finally, the recursive case breaks the first list into its head (x) and tail (xs) and says that to concatenate the two lists, concatenate the tail of the first list with the second list, and then tack the head x on the front.

There's a pattern here: with list-based functions, the base case usually involves an empty list, and the recursive case involves passing the tail of the list to our function again, so that the list becomes progressively smaller.

Exercises

Give recursive definitions for the following list-based functions. In each case, think what the base case would be, then think what the general case would look like, in terms of everything smaller than it. (Note that all of these functions are available in Prelude, so you will want to give them different names when testing your definitions in GHCi.)

  1. replicate :: Int -> a -> [a], which takes a count and an element and returns the list which is that element repeated that many times. E.g. replicate 3 'a' = "aaa". (Hint: think about what replicate of anything with a count of 0 should be; a count of 0 is your 'base case'.)
  2. (!!) :: [a] -> Int -> a, which returns the element at the given 'index'. The first element is at index 0, the second at index 1, and so on. Note that with this function, you're recursing both numerically and down a list[5].
  3. (A bit harder.) zip :: [a] -> [b] -> [(a, b)], which takes two lists and 'zips' them together, so that the first pair in the resulting list is the first two elements of the two lists, and so on. E.g. zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]. If either of the lists is shorter than the other, you can stop once either list runs out. E.g. zip [1,2] "abc" = [(1, 'a'), (2, 'b')].

  4. Define length using an auxiliary function and an accumulating parameter, as in the loop-like alternate version of factorial.

Recursion is used to define nearly all functions to do with lists and numbers. The next time you need a list-based algorithm, start with a case for the empty list and a case for the non-empty list and see if your algorithm is recursive.

Don't get TOO excited about recursion...Edit

Although it's very important to have a solid understanding of recursion when programming in Haskell, one rarely has to write functions that are explicitly recursive. Instead, there are all sorts of standard library functions which perform recursion for you in various ways, and one usually ends up using those instead. For example, a much simpler way to implement the factorial function is as follows:

Example: Implementing factorial with a standard library function

factorial n = product [1..n]

Almost seems like cheating, doesn't it? :) This is the version of factorial that most experienced Haskell programmers would write, rather than the explicitly recursive version we started out with. Of course, the product function is using some list recursion behind the scenes,[6] but writing factorial in this way means you, the programmer, don't have to worry about it.


NotesEdit

  1. In mathematics, n! normally means the factorial of a non-negative integer n, but that syntax is impossible in Haskell, so we don't use it here.
  2. Actually, defining the factorial of 0 to be 1 is not just arbitrary; it's because the factorial of 0 represents an empty product.
  3. Interestingly, older scientific calculators can't handle things like factorial of 1000 because they run out of memory with that many digits!
  4. This is no coincidence; without mutable variables, recursion is the only way to implement control structures. This might sound like a limitation until you get used to it.
  5. Incidentally, (!!) provides a reasonable solution for the problem of the fourth exercise in Lists and tuples/Retrieving values.
  6. Actually, it's using a function called foldl, which actually does the recursion.