Haskell/Recursion
Recursion plays a central role in Haskell (and computer science and mathematics in general): recursion is the idea of defining a function in terms of itself. A function defined in this way is said to be recursive.
Recursion is merely a form of repetition, but sometimes it is taught in a confusing or obscure way. It is simple enough to understand as long as you separate the meaning of a recursive function from its behaviour.
Recursion, like other forms of repetition, require a stopping or termination condition. Like an infinite loop, a badly designed recursive function might lead to infinite regress; but if done properly it won't.
Generally speaking, a recursive definition has two parts. First, there are one or more base cases which express termination conditions, and the value of the function when the termination condition holds; it is essential that the base case does not call the function being defined. The recursive case is more general, and defines the function in terms of a 'simpler' call to itself. If we think of a function as being the solution to a computational problem, the recursive case expresses the relationship between the solution to a given problem and the solution of a somewhat smaller or simpler problem of the same kind. To make this idea more concrete, let's look at a few examples.
Numeric recursion[edit]
The factorial function[edit]
In mathematics, especially combinatorics, there is a function used fairly frequently called the factorial function^{[1]}. It takes a single nonnegative 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 ) is . This is an interesting function for us, because it is a candidate to be written in a recursive style.
The idea is to look at the factorials of 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 involves the . In fact, is just . 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
Indeed, we can see that the factorial of any number is just that number multiplied by the factorial of the number one less than it. There's one exception to this: if we ask for the factorial of 0, we don't want to multiply 0 by the factorial of 1 In fact, we just say the factorial of 0 is 1 (we define it to be so. It just is, okay^{[2]}?). So, 0 is the base case for the recursion: when we get to 0 we can immediately say that the answer is 1, without using recursion. 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 (n1)
This defines a new function called factorial
. The first line says that the factorial of 0 is 1, and the second one says that the factorial of any other number n
is equal to n
times the factorial of n1
. Note the parentheses around the n1
: without them this would have been parsed as (factorial n)  1
; function application (applying a function to a value) will happen before anything else does (we say that function application binds more tightly than anything else).
The factorial function written above should be defined in a file. Since it is a small function, however, it is not too unreasonable to write it in GHCi as a oneliner, by using braces (that is, { and } ) and a semicolon:
> let { factorial 0 = 1; factorial n = n * factorial (n  1) } let statements without the braces in the interpreter will cause the function to be redefined with the last definition, losing the important first definition and thus leading to infinite recursion. 
If this seems confusing to you, try to separate the meaning of the definition from the behaviour of the computer while executing a recursive function. The examples above demonstrate a very simple relationship between factorial of a number, n, and the factorial of a slightly smaller number, n1. This relationship only needs to be understood at a single abstract level.
But understanding the relationship is only one side of the issue. We do need to understand how recursive functions behave. Think of a function call as delegation. The instructions for a recursive function delegate a subtask. It just so happens that the delegate function uses the same instructions as the delegator. It's just the input data that changes. The only really confusing thing about the behaviour of a recursive function is the fact that each function call uses the same parameter names, and it can be tricky for a person to keep track of where they are.
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).
 1 isn't 0, so we calculate the factorial of 0
 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).
 2 isn't 0, so we calculate the factorial of 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).
We can see how the result of the recursive call is calculated first, then combined using multiplication. Once you see how it can work, you 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, e.g., the relationship between factorial n
and factorial (n1)
.
(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 one 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.)
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. In this case, 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. So factorial 0
would match the general n
case, the compiler would conclude that factorial 0
equals 0 * factorial (1)
, and so on to negative infinity. Definitely not what we want. The lesson here is that one should always list multiple function definitions starting with the most specific and proceeding to the most general.
Exercises 


A quick aside[edit]
 This section is aimed at people who are used to more imperativestyle languages like e.g. C.
Loops are the bread and butter of imperative languages. For example, the idiomatic way of writing a factorial function in an imperative language would be to use a for loop, like the following (in C):
Example: The factorial function in an imperative language
int factorial(int n) { int res = 1; for ( ; n > 1; n) res *= n; return res; }
This isn't directly possible in Haskell, 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 a parameter of a recursive function. For example, here is a direct 'translation' of the above loop into Haskell:
Example: Using recursion to simulate a loop
factorial n = factorialWorker n 1 where factorialWorker n res  n > 1 = factorialWorker (n  1) (res * n)  otherwise = res
Obviously this is not the shortest or most elegant way to implement factorial
in Haskell (translating directly from an imperative paradigm into Haskell like this rarely is), but it can be nice to know that this sort of translation is always possible.
Another thing to note is that you shouldn't be worried about poor performance through recursion with Haskell. In general, functional programming compilers include a lot of optimisation for recursion, including an important one called tailcall optimisation; remember too that Haskell is lazy – if a calculation isn't needed, it won't be done. We'll learn about these in later chapters.
Other recursive functions[edit]
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 n 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 recursively calling the function 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), but it doesn't have to be; the smaller argument could be produced in some other way as well.
Exercises 


Listbased recursion[edit]
A lot of functions in Haskell turn out to be recursive, especially those concerning lists^{[3]}. Let us 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 us explain the algorithm in English to clarify how it works. The type signature of length
tells us that it takes any sort 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 consists of a first element, x
, and xs
, the rest of the list, the length of the list is one plus the length of xs
(as in the head
/tail
example in Haskell/Next steps, x
and xs
are set when the argument list matches the (:) pattern).
How about the concatenation function (++)
, which joins two lists together? (Some examples of usage are also given, as we haven't come across this function so far in this chapter.)
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 you break it down. The type says that (++)
takes two lists and produces another. 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 listbased 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 listbased 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.)

Recursion is used to define nearly all functions to do with lists and numbers. The next time you need a listbased algorithm, start with a case for the empty list and a case for the nonempty 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^{[5]}, but writing factorial
in this way means you, the programmer, don't have to worry about it.
Summary[edit]
Recursion is the practice of defining a function in terms of the function itself. It nearly always comes in two parts: a base case and a recursive case. Recursion is especially useful for dealing with list and numberbased functions.
Notes[edit]
 ↑ In mathematics, n! normally means the factorial of a nonnegative integer, n, but that syntax is impossible in Haskell, so we don't use it here.
 ↑ Actually, defining the factorial of 0 to be 1 is not just arbitrary; it's because the factorial of 0 represents an empty product.
 ↑ 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 (it isn't, really).
 ↑ Incidentally,
(!!)
provides a reasonable solution for the problem of the fourth exercise in Lists and tuples/Retrieving values.  ↑ Actually, it's using a function called
foldl
, which actually does the recursion.