CSCI 2610 Lecture 7 Notes

Recursion

Sometimes, you can solve a computational problem by asking a friend to solve a slightly smaller problem of the same kind. For example, to compute 10! = 1x2x3x...x9x10, you can ask a friend to compute 9!. Then you just multiply that result by 10.

If this is the way that you choose to solve factorials, then your friend will employ the same method. To compute 9!, he or she will call up yet another friend, asking for the value of 8!. That friend will call up yet another friend for 7!, and this process will continue until somebody is asked for the value of 1!.

When asked to compute 1!, there is no need to ask for help. The answer is 1.

This idea can be used in computer programs. A function can call itself. When it does, it really is calling a clone of itself. As many clones as are needed will be created (up to the capacity of the computer to store them).

For example, here is a definition (and contract) for a function that computes factorials. 

   ////////////////////////////////
   //           factorial        //
   ////////////////////////////////
   // factorial(n) returns n!.   //
   ////////////////////////////////

   long factorial(long n)
   {
     if(n == 1) return 1;
     else return factorial(n-1) * n;
   }
The factorial function calls itself. This is called recursion. When factorial calls factorial, it is said to do a recursive call.

Designing recursive functions

Here are some important rules to use when designing recursive functions.

  1. Always have a case where you don't do a recursive call. This is called the basis case of the definition. It is necessary to stop the process of asking for help, and to get some answers to be computed.

  2. Always write a contract for the function before you write the function implementation. This is very important, since it is the contract that tells what the recursive calls do. You need to write the recursive calls before you are done writing the entire function implementation, so you can't possibly read the (incomplete) function implementation to see what the function does.

  3. When you think about what a recursive call will do, think in terms of what the contract says it will do. Presume that the recursive calls work.

  4. Make sure that each recursive call is asked to solve a smaller problem than you are working on. For example, when you are trying to compute 10!, you ask somebody else to compute 9!. That is fine, since computing 9! is a smaller problem than computing 10!. It is not reasonable to ask somebody else to do the entire job of computing 10!, since then they will do the same thing, and nobody will ever take responsibility for doing any work.

An example: computing powers

Suppose that you want to compute x^n (x to the n-th power), where n is a positive integer. To do this, break the problem into two cases.

  1. (case where no help is needed) If n = 1, then x^n = x.

  2. (case where help is needed) If n > 1, then x^n = x*x^(n-1). So to compute x^n, ask a friend to compute x^(n-1), and then multiply that result by x.

Asking a friend to compute x^(n-1) can be done in the function implementation by letting the function call itself. Remember that what it really does is call a copy of itself. Here is the power function. 

    /////////////////////////////////////////////
    //                 power                   //
    /////////////////////////////////////////////
    // power(x,n) returns x to the n-th power. //
    //                                         //
    // Requirement: n must be a positive       //
    // integer.                                //
    /////////////////////////////////////////////

    double power(double x, int n)
    {
      if(n == 1) return x;
      else return x * power(x, n-1);
    }

An improved power function

You can save a lot of time in computing powers by noting that, when n is even, x^n = (x^(n/2))^2. For example, x^16 = (x^8)^2. You can compute x^16 by computing x^8 once, and multiplying that by itself. This saves a lot of multiplications. (Computing x^16 by the standard method requires 15 multiplications. Computing x^16 by the improved method takes only 4 multiplication. The savings is even more dramatic for larger n. Only 10 multiplications are needed to compute x^1024.)

This improvement is very easy to add to the recursive implementation of the power function. Notice that the contract does not change, since we are computing the same function, but doing so more efficiently. 

    /////////////////////////////////////////////
    //                 power                   //
    /////////////////////////////////////////////
    // power(x,n) returns x to the n-th power. //
    //                                         //
    // Requirement: n must be a positive       //
    // integer.                                //
    /////////////////////////////////////////////

    double power(double x, int n)
    {
      if(n == 1) return x;
      else if(n % 2 == 0) {
        double p = power(x,n/2);
        return p*p;
      }
      else return x * power(x, n-1);
    }
It might be useful to see whether you can implement the same thing using a loop instead of recursion. It can be done, but it is much more difficult.

Another example

Suppose that you want to read a list of numbers, terminated by a 0, and to print the numbers (excluding the 0) in reverse order. For example, if the input is as shown, the output would be as shown.
input      output
7      15
9      4
4      9
15      7
0
To do this, you can read the first number from the input (the 7 in the example), then ask a friend to do exactly the same job. The friend will, according to the statement of the problem, read the remaining numbers and print them backwards. In the example, your friend will read 9, 4, 15 and 0, and will print 15, 4 and 9, in that order. To finish, you just print the 7.

There is a simple case where you don't need to ask for help. If the input contains only a 0, then you don't need to print anything at all. These ideas are implemented in the following function definition. 

    ////////////////////////////////////////////////////
    //                   PrintReverse                 //
    ////////////////////////////////////////////////////
    // PrintReverse() reads numbers up to a 0, and    //
    // prints the numbers read in reverse order,      //
    // one number per line, excluding the 0.  For     //
    // example if the input is a shown below, the     //
    // output would be as shown.                      //
    //                                                //
    //    input            output                     //
    //    -----            ------                     //
    //       7                15                      //
    //       9                 4                      //
    //       4                 9                      //
    //      15                 7                      //
    //       0                                        //
    ////////////////////////////////////////////////////

    void PrintReverse()
    {
      int x;
      cin >> x;
      if(x != 0) {
         PrintReverse();
         cout << x << endl;
      }
    }

Remarks on recursion

Recursion is an alternative to looping. Do not try to do both recursion and looping in the same function.

A recursive function generally starts with an if statement, which determines whether the current case is so simple that no recursion is required, or is sufficiently complex that recursion should be used. Look at the example. They all do such an if statement.

In some function definitions, there are more than two cases. The improved power function is an example.