Recursion and recursive algorithms

While trying to solve the problem,
I found obstacles within obstacles.
Therefore, I opted for a recursive solution.

— a student

To understand recursion,
we must first understand recursion.

— anonymous

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:

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.

Table of contents:

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

  1. What kind of problem can be solved by a recursive algorithm?
  2. Consider the function rmaximum above.  Does it make sense to replace  return v[0]  by  return 0?  Does it make sense to replace  return v[0]  by  return INT_MIN?  Does it make sense to replace  x > v[n-1]  by  x >= v[n-1]?
  3. Consider the function rmaximum above.  If the array v[0..n-1] has two or more largest elements, which of them will the function return?
  4. In the worst case, how many comparisons involving elements of the array will the function rmaximum do?
  5. Check that the following code is exactly equivalent to the code of function rmaximum given above:
    int rmaximum (int n, int v[]) {
       int x;
       if (n == 1) x = v[0];
       else {
          x = rmaximum (n-1, v); 
          if (x < v[n-1]) x = v[n-1];
       }
       return x;
    }
    
  6. Check that the following code is exactly equivalent to the code of function rmaximum given above:
    int rmaximum (int n, int v[]) { 
       if (n == 1) return v[0];
       int x = rmaximum (n-1, v);
       if (x > v[n-1]) return x;
       else return v[n-1]; 
    }
    
  7. Criticize the following recursive function, that promises to find the value of a largest element of v[0..n-1]:
    int maxim1 (int n, int v[]) {       
       if (n == 1) return v[0];    
       if (n == 2) {
          if (v[0] < v[1]) return v[1];
          else return v[0];
       }
       int x = maxim1 (n-1, v);
       if (x < v[n-1]) return v[n-1];
       else return x;
    }
    
  8. Criticize the following recursive function, that promises to find the value of a largest element of v[0..n-1]:
    int maxim2 (int n, int v[]) {
       if (n == 1) return v[0];
       if (maxim2 (n-1, v) < v[n-1]) 
          return v[n-1];
       else 
          return maxim2 (n-1, v);
    }
    
  9. Test program.  Write a small program to test the function rmaximum given above.  Your program must generate a random array and find the value of a largest element of the array. Add to your program a function that will check the answer given by rmaximum.  [Solution: ./solutions/recu2.html#part2]
  10. Write a recursive function maxmin to calcule the value of a largest and a smallest elements of an array v[0..n-1]. How many comparisons involving elements of the array will your function do?

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

  1. Consider the function maximum2 above.  If the array v[0..n-1] has two or more largest elements, which will the function find and return?  What if we replace if (x > v[i]) by if (x >= v[i])?
  2. The following recursive function promises to find the value of a largest element of v[p..r] assuming p ≤ r.  Is the function correct?  Suppose that p and r are 0 and 6 respectively and show the (duly indented) sequence of calls to rmaxx.
    int rmaxx (int p, int r, int v[]) {
       if (p == r) return v[r];
       else {
          int q, x, y;
          q = (p + r)/2; // p ≤ q < r
          x = rmaxx (p, q, v);
          y = rmaxx (q+1, r, v);
          if (x >= y) return x;
          else return y;
       }
    }
    

Exercises 3

  1. Write a recursive function to calcule the sum of the positive elements of an integer array v[0..n-1].  Does the problem make sense when n is equal to 0?  What is the sum in this instance?
  2. Criticize the documentation of the following function:
    // Receives an array of size n and returns 
    // the sum of the elements of the array.
    int sum (int v[], int n) {
       return sss (v, n+1); 
    }
    int sss (int v[], int n) {
       if (n == 1) return 0;
       return sss (v, n-1) + v[n-1]; 
    }
    
  3. Say what the function below does.  For what values of the parameters is your answer correct?
    int ttt (int x[], int n) {
       if (n == 0) return 0;
       if (x[n] > 100)  return x[n] + ttt (x, n-1);
       else  return ttt (x, n-1);
    }
    
  4. Write a recursive function to compute the product of the strictly positive elements of an integer array v[0..n-1].  Does this problem make sense when all the elements of the array are null?  Does this problem make sense when n is 0?  What is the value of the product in these two instances?
  5. Write a recursive function to calcule the sum of the decimal digits of a strictly positive integer n. (For example, the sum of digits of 132 is 6.)
  6. Write a recursive function to calcule the floor of the logarithm of N in base 2.  (See a non recursive version of the function.)

Exercises 4

  1. What is the value of X (4) when X is given by the following code?
    int X (int n) {
       if (n == 1 || n == 2) return n;
       else return X (n-1) + n * X (n-2);
    }
    
  2. What is the value of f (1,10)? Write an equivalent but simpler function.
    double f (double x, double y) {
       if (x >= y) return (x + y)/2;
       else return f (f (x+2, y-1), f (x+1, y-2));
    }
    
  3. What is the result of the execution of the following program?
    int ff (int n) {
       if (n == 1) return 1;
       if (n % 2 == 0) return ff (n/2);
       return ff ((n-1)/2) + ff ((n+1)/2);
    }
    int main (void) {
       printf ("%d", ff(7)); 
       return EXIT_SUCCESS;
    }
    
  4. Execute fsc (7,0). Show the duly indented sequence of the calls to fsc.
    int fsc (int n, int depth) {
      for (int i = 0; i < depth; ++i) 
         printf ("  ");
      printf ("fsc(%d,%d)\n", n, depth);
      if (n = 1) 
         return 1;
      if (n % 2 == 0) 
         return fsc (n/2, depth+1);
      return fsc ((n-1)/2, depth+1) + 
             fsc ((n+1)/2, depth+1);
    }
    
  5. ★ Criticize the following recursive function:
    int XX (int n) {
       if (n == 0) return 0;
       else return XX (n/3+1) + n;
    }
    
  6. Fibonacci.  The Fibonacci function is defined as follows:  F(0) = 0F(1) = 1,  and  F(n) = F(n-1) + F(n-2)  for n > 1. Define function F in C language. Write a recursive and an iterative versions.
  7. Let F be a recursive version of the Fibonacci function.  The calculation of the value of the expression F(3) leads to the following sequence of calls to the function:
       F(3)
          F(2)
             F(1)
             F(0)
          F(1)
    
    What is the sequence of calls to the function produced by the calculation of F(5)?
  8. Euclid.  The following function computes the greatest common divisor of strictly positive integers m and n. Write an equivalent recursive function.
    int Euclid (int m, int n) {
       int r;
       do {
          r = m % n; 
          m = n; 
          n = r;
       } while (r != 0);
       return m; 
    }
    
  9. Exponentiation.  Write an efficient recursive function that will receive strictly positive integers k and n and compute kn.  (You may assume that kn fits in an int.)  How many multiplications does your function execute approximately?
    .
    . -
    . --
    . -
    . ---
    . -
    . --
    . -
    . ----
    . -
    . --
    . -
    . ---
    . -
    . --
    . -
    .
    
  10. Ruler [Sedgewick, Roberts].  Write a recursive function to print a ruler of order n in the interval [0 .. 2n].  The tick at the midpoint of the ruler must have length n; the ticks at the midpoints of the upper and lower subintervals must have length n−1; and so on.  The figure shows a ruler of order 4.

Questions and answers