Recursion

The similarity of problems to their solutions

When you think about a problem that you want to solve by a computer program, you often see some features of the problem that suggest how to solve it.

1. Suppose that the problem is to print two lines of text. This obviously breaks down into two parts: print the first line, then print the second line. You can work on each line separately.

   Doing one thing after another is called sequencing, which you do in a Java program by writing one part after another in a method.

2. Suppose that a problem is expressed as a collection of cases. For example, the definition of a prime number can be expressed as follows.

   1. If n < 2, then n is not prime.
   2. If n >= 2, then n is prime provided n is not composite.

   When a problem naturally breaks down into cases, you solve it using an if-else statement. Here is a method that tests whether a number is prime.

       //=======================================
       // isprime(n) returns true if n is prime
       // and false otherwise.
       //=======================================
   
       public static boolean isprime(long n)
       {
         if(n < 2) return false;
         else return !composite(n);
       }
     

3. Some problems naturally suggest doing something over and over. For example, the problem of computing xⁿ can be solved by starting with 1, and then multiplying by x a total of n times. You can write 1*xⁿ = x * ... * x (n copies of x)

   Any time you see ..., or when the problem is expressed in terms of repeating something, you should think of a loop. So a definition of power is as follows, with a loop.

      //========================================
      // power(x,n) returns x to the n-th power.
      // REQUIREMENT: n >= 0.
      //========================================
   
      public static long power(long x, long n)
      {
        long k, result;
        result = 1;
        k = 0;
        while(k < n) 
        {
          result = result * x;
          k = k + 1;
        }
      }
     

Recursion in problems

Some problems have a form where you can find smaller versions of the same kind of problem within the problem, as long as the specific problem is not too small. Here are some examples.

1. When n > 0, you can notice that

   xⁿ = x * x^n-1.

   So the problem of computing xⁿ contains the smaller problem of computing x^n-1. If you ask someone else to tell you the value of x^n-1, then you can find xⁿ by doing one more multiplication.

   (You cannot find a smaller problem of the same kind inside x⁰. But that is ok, because you know that x⁰ = 1.)

   ---

2. Suppose that you want to compute 1 + 2 + ... + n. Notice, for n > 0,

   1 + 2 + ... + n = (1 + 2 + ... + (n-1)) + n

   Again, you see that, if you could ask somebody else to compute (1 + 2 + ... + (n-1)), then you could compute the answer to the slightly larger problem (1 + 2 + ... + n) by doing one more addition.

   If n is 0, then you cannot break the problem down. But that is ok, because the sum of the first 0 integers is 0, and you do not need any help.

   ---

3. Suppose that you want to print the prime numbers that are less than or equal to n. As long as n > 1, you could do this as follows.

   1. Ask somebody else to print the prime numbers that are less than or equal to n-1.

   2. If n is prime, then print n.

   But if n is 1, you do not print anything, since there are no prime numbers that are less than or equal to 1.

   ---

4. (This example looks ahead to arrays.) Suppose that you to sort the members of an array into ascending order.

   When you use an array, you do not always put something in every slot. Part of the array is typically occupied, and part is vacant, waiting for you to add more later. So a more natural problem is to sort the first n members of an array, ignoring the rest. For example, you might be asked to sort the first 20 members of an array that has 50 slots in it.

   Suppose that n > 1. Then, to sort the first n members of array a,

   1. Ask somebody else to sort the first n-1 members of the array.

   2. Put the n-th member into the correct position, realizing that the first n-1 members are in the correct order already.

   For the case where n is 1, you do not really have any problem, since an array of only one slot is automatically sorted without doing anything.

   ---

It turns out to be very common for problems to have smaller versions of the same problem inside themselves. When you can identify this in a problem, you use recursion to solve the problem.

Recursion is nothing but the ability of a function to use itself. What it really uses is a copy of itself, with different variables.

Example: power

The following function definition makes use of the recursive structure of the power function.

   //========================================
   // power(x,n) returns x to the n-th power.
   // REQUIREMENT: n >= 0.
   //========================================

  public static long power(long x, long n)
  {
    if(n == 0) return 1;
    else return x * power(x, n-1);
  }

Example: sum

  //=============================
  // sum(n) = 1 + 2 + ... + n
  //=============================

  public static long sum(long n)
  {
    if(n == 0) return 0;
    else return sum(n-1) + n;
  }

Example: print primes

  //==================================================
  // printPrimes(n) prints the prime numbers that are
  // less than or equal to n.
  //==================================================

  public static void printPrimes(long n)
  {
    if(n > 1) 
    {
      printPrimes(n-1);
      if(isprime(n)) 
      {
        System.out.println(n);
      }
    }
  }

Example: sort an array

  //===============================================
  // insert(a,n) sorts a[0,...,n-1] into ascending
  // (or nondescending) order.
  //
  // REQUIREMENT.
  //   1. n >= 1.
  //   2. If n >= 2 then a[0,...,n-2] is already sorted.
  //===============================================

  private static void insert(int[] a, int n)
  {
    if(n > 1 && a[n-1] < a[n-2]) 
    {
      // Swap a[n-1] with a[n-2], then sort a[0,...,n-2].

      int t = a[n-1];
      a[n-1] = a[n-2];
      a[n-2] = t;
      insert(a, n-1);
    }
  }

  //==============================================
  // sort(a,n) sorts a[0,...,n-1] into ascending
  // (or nondescending) order.
  //==============================================

  public static void sort(int[] a, int n)
  {
    if(n > 1) 
    {
      sort(a, n-1);
      insert(a, n);
    }
  }

Notice that the insert method also uses recursion inherent in a problem. Suppose that you know that a[0,...,n-2] is already sorted, and you want to sort a[0,...,n-1]. Here is an example, with n = 5.