Algorithms Design   |   C language   |   Index

Recursion and recursive algorithms

Many computational problems have the following property: every instance of the problem contains a smaller instance of the same problem. We say that such problems have recursive structure.  To solve an instance of a problem of this kind, we can use the following method:

• if the instance is small,

  solve it directly (use brute force if needed);

• else

  reduce it to a smaller instance of the same problem,

  apply the method to the smaller instance,

  return to the original instance.

The programmer only needs to show how to obtain a solution of the original instance from a solution of the smaller instance;  the computer will do the rest.  An application of this method produces a recursive algorithm.

Largest element of an array

To illustrate the concept of recursive algorithm, consider the following problem:  Find the value of a largest element of an array  v[0..n-1].  (This problem has already been mentioned in one of the exercises in the Arrays chapter.)

Notice that the problem only makes sense if the array is not empty, that is, if n ≥ 1.  Here is a recursive function that solves the problem:

// After receiving v and n >= 1, the function
// returns the value of a largest element of
// the array v[0..n-1].

int 
rmaximum (int n, int v[])
{ 
   if (n == 1)
      return v[0];
   else {
      int x;
      x = rmaximum (n-1, v);
      // x is largest in v[0..n-2] 
      if (x > v[n-1]) return x;
      else return v[n-1]; 
   }
}

The correctness analysis of the function takes the form of a proof by induction.  To begin with, consider an instance in which n is 1. In this instance, the function returns the correct answer, v[0].  Now consider an instance in which n is greater than 1. In this instance, the array has two nonempty parts:

v[0..n-2]  and  v[n-1].

We may assume that the function solves correctly the instance v[0..n-2] of the problem, since this instance is smaller than the original one. Therefore, after the line x = rmaximum (n-1, v), we may assume that x is the value of a largest element of v[0..n-2]. Hence, the solution of the original instance is the larger of x and v[n-1]. And this is precisely the number that the function computes and returns.  This concludes the proof of correctness of the rmaximum function.

For a recursive function to be undestandable, the author of the function must state what is it that the function does. And he must state it explicitly and in detail, as I did above in the comment that precedes the code of the function.

How does a computer execute a recursive function?  Though relevant and important, this question will be ignored for now. (But you can see the appendix The execution stack of a program in the Stacks chapter.)  We shall only examine an example of execution. If v[0..3] is the array  77 88 66 99 , we shall have the following sequence of calls to the function:

rmaximum(4,v)
│ rmaximum(3,v) 
│ │ rmaximum(2,v) 
│ │ │ rmaximum(1,v)
│ │ │ └──────────── returns 77
│ │ └────────────── returns 88
│ └──────────────── returns 88
└────────────────── returns 99

Performance.  Some people believe that recursive functions are inherently slow, but this is just an urban legend.  The legend may have its origin in some careless programming, as in some of the exercises below.  (Not all is rosy, however: the memory space that a recursive function consumes for bookkeeping can be large.)

Exercises 1

Another solution

The function rmaximum discussed above reduces the instance v[0..n-1] of the problem to the instance v[0..n-2].  Instead, we can write a function that will reduce v[0..n-1] to v[1..n-1]:

// Upon receiving v and n >= 1, this
// function returns the value of a
// largest element of v[0..n-1].

int 
maximum2 (int n, int v[]) 
{
   return rmax (0, n, v);
}

The function maximum2 is just a wrapper; the job proper is done by the recursive function rmax:

// Receives v and i < n and returns the
// value of a largest element of
// v[i..n-1].

int 
rmax (int i, int n, int v[]) 
{
   if (i == n-1) return v[i];
   else {
      int x;
      x = rmax (i + 1, n, v);
      if (x > v[i]) return x;
      else return v[i]; 
   } 
}

The function rmax solves a problem more general than the original one (notice the parameter i).  The need to generalize the original problem arises quite often in the design of recursive algorithms.

As a matter of curiosity, here is another, perhaps surprising, way of applying recursion to the segment v[1..n-1] of the array.  It uses address arithmetic instead of the extra parameter i.

int rmaximum2b (int n, int v[]) {
   if (n == 1) return v[0];
   int x = rmaximum2b (n - 1, v + 1);
   if (x > v[0]) return x;
   return v[0];
}

Exercises 2

Exercises 3

Exercises 4