Worksheet 4: Recurrences and recursion

Suppose we want to draw rows of men of different lengths. It would be useful to have a function manrow(n) that, for any value of n, would give a row of n men. How can we define this function so that it works for any value of n .

For example manrow(4) would be a row of 4 men; let's call that picture r4:

define r4 = man $ man $ man $ man

Similarly, let us call a row of five men r5:

define r5 =
  man $ man $ man $ man $ man

What relates r4 and r5? How can we go from a row of four men to a row of five men? We just need to add another man! So we can say:

r5 = r4 $ man.

Similarly, we can say that r4 = r3 $ man if r3 is a row of three men.

Writing your answers in the same way, work out equations for r3 and r2.

The expression r1 refers to a row of just one man, which is the same as the expression man. Hence we should write the equation

r1 = man.

It would be ideal if we could define a function manrow that can take a number as an argument, and produce a row of men that is as long as that number. The way to do this is tricky to understand, so look at the definition below, and then read the explanation that follows it:

define manrow(n) = manrow(n-1) $ man when n > 1
  | manrow(1) = man;

This definition of the function manrow consists of two equations, separated by a vertical bar character |. The first equation is used when n > 1, and states in general form our observations that r4 = r3 $ man, and r3 = r2 $ man, and so on. The other equation is simpler, and just restates the fact that r1 = man in terms of the function manrow.

You should enter this definition into GeomLab. On a British PC keyboard, the symbol | is entered by holding down the Shift key and pressing the \ key, just to the left of the Z. At first sight, this equation appears to be defining the function manrow in terms of itself, and because of this, we call it a recursive definition. Despite the self-reference, the definition works because it shows us how to calculate, say, manrow(5) assuming we already know how to calculate manrow(4), and applying the equation repeatedly can bring us down to the base case manrow(1) = man.

Having defined manrow as aboive, if you type an expression like manrow(5), then GeomLab expands the definition like this:

manrow(5) = manrow(4) $ man
  = manrow(3) $ man $ man
  = manrow(2) $ man $ man $ man
  = manrow(1) $ man $ man $ man $ man
  = man $ man $ man $ man $ man.

The result is the image we expected:

manrow(5)

What does manrow(4) & manrow(3) & manrow(2) look like? Sketch the picture here:

manrow(4) & manrow(3) & manrow(2)

This picture looks a bit like a crowd, so let's try to define a function that can create crowds of different sizes.

To get a realistic-looking crowd, we will need to have rows that get larger in the number of men (and smaller in height) as we travel from bottom to top of the picture. The function crowd(m, n) can be defined so that m is the length of the bottom row in the picture, and n is the length of the top row. To save ourselves work, we can use the previously defined function manrow to draw the rows that we want.

If m and n are the same, then the crowd will consist of just one row:

crowd(m, m) = manrow(m)

Otherwise, we are considering an expression of the form crowd(m, n), where m < n. This crowd consists of a top row containing n men, and below it a smaller crowd with rows ranging from m to n-1 men:

crowd(m, n) = manrow(n) & crowd(m, n-1)

We can put these two equations together to make a recursive definition of the function crowd:

define crowd(m, n) = manrow(n) & crowd(m, n-1) when m < n
  | crowd(m, m) = manrow(m)

Here are two example images produced using our crowd function:

crowd(3, 5)
crowd(6, 12)

Try it, by putting the definitions of both manrow and crowd together one with one of these expressions, all in the same text.

This sheet has introduced an important new idea: that we can take a recurrence relation that describes a sequence of pictures, and turn it into the definition of a recursive function that generates pictures in the sequence. Simple recursive definitions have two parts: a rule that generates an element of the sequence from the previous element, and a starting rule that defines the first element. The idea of defining functions recursively is important, because it opens the possibility that a finite program can generate an infinite variety of behaviour by varying the argument that is passed to the function.

With a non-recursive function, each time the function is referred to, the formula that is the body of the function is used just once. With a recursive function, substituting the body of the function for a use of it may leave a formula that still contains a use of the function, so the definition may be used many times in computing the value of the function. In a wider setting, it is recursion that lets us use functions to model, understand, and compute with complex processes.