School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring06 Prof. Michael B. Feldman mfeldman@gwu.edu

You know that a function can call another function; that is, a statement in the body of a function F contains a call of another function G. What would happen if a statement in F contained a call of F? This situation—a function or procedure calling itself—is not only permitted but in fact is very interesting and useful. The concept of a subprogram—a function or a procedure—calling itself is a mathematical concept called recursion, and a subprogram that contains a call to itself is called a recursive subprogram.

Recursion can be an alternative to iteration (looping), although a recursive solution to a given problem uses somewhat more computer time and space than an iterative solution to the same problem; this is due to the overhead for the extra calls. However, in many instances the use of recursion enables us to specify a natural, simple solution to a problem that would otherwise be difficult to solve. For this reason, recursion is an important and powerful tool in problem solving and programming.
 

The Nature of Recursion

• One or more simple cases of the problem (called stopping cases) have a simple, nonrecursive solution.
• For the other cases, there is a process (using recursion) for substituting one or more reduced cases of the problem that are closer to a stopping case.
• Eventually the problem can be reduced to stopping cases only, all of which are relatively easy to solve.

    if (the stopping case is reached)
    { 
        Solve it
    }
    else
    {
        Reduce the problem using recursion
    }

Figure 1
Splitting a Problem into Smaller Problems
 

Recursive Multiplication

Problem 1. Multiply 6 by 2.

Problem 2. Add 6 to the result of problem 1.

Because we know the addition tables, we can solve problem 2 but not problem 1. However, problem 1 is simpler than the original problem. We can split it into the two problems 1.1 and 1.2, leaving us three problems to solve, two of which are additions.

 Problem 1. Multiply 6 by 2.

     Problem 1.1 Multiply 6 by 1.

     Problem 1.2 Add 6 to the result.

Problem 2. Add 6 to the result of problem 1.

Even though we don't know the multiplication tables, we are familiar with the simple rule that, for any M, M x 1 is M. By solving problem 1.1 (the answer is 6) and problem 1.2, we get the solution to problem 1 (the answer is 12). Solving problem 2 gives us the final answer, 18.

The Java function Multiply shows this:

  public static int Multiply (int M, int N)
  {

    // Performs multiplication recursively using the + operator
    // Pre : M and N are defined and N > 0
    // Post: returns M * N

    int Result;

    if (N == 1)
    {
      Result = M;                     // stopping case
    }
    else
    {
      Result = M + Multiply(M, N-1);  // recursion
    }

    return Result;

  }

The program TestMultiply.java illustrates how Multiply might be called to produce the multiplication table for the integers 1 through 5:

//--------------------------------------------------------------
//| TestMultiply.java
//| Illustrates recursive Multiply algorithm
//| Author: M.B. Feldman, The George Washington University
//| Last Modified: March 2003
//--------------------------------------------------------------
import cs1.Keyboard;
public class TestMultiply
{

  public static int Multiply (int M, int N)
  {

    // Performs multiplication recursively using the + operator
    // Pre : M and N are defined and N > 0
    // Post: returns M * N

    int Result;

    if (N == 1)
    {
      Result = M;                     // stopping case
    }
    else
    {
      Result = M + Multiply(M, N-1);  // recursion
    }

    return Result;

  }

  public static void main (String[] args)
  {

    for (int Num1 = 1; Num1 <= 5; Num1++)
    {
      for (int Num2 = 1; Num2 <= 5; Num2++)
      {
        System.out.print(Multiply(Num1, Num2) + "\t");
      }
      System.out.println();
    }
  }
}
 
 

Factorial

To find N!:

1. If N = 1 then N!  = 1;
2. Otherwise N! = N x (N - 1)!

Recursive Calculation of 5!

Try the definition on some other numbers to make sure you understand how the recursion works. You will discover that N! gets very large very quickly: Even an innocent-looking calculation, such as 10!, produces a rather large number (3,628,800). In fact, if you were to write a program to calculate N! and run it on a computer using 16 bits to represent an integer, your program could not calculate factorials larger than 7!, because 8! > 32767. On a computer with a 32-bit integer representation, your program would fail to compute 14!.

Here is a recursive Java function to compute the factorial of a positive number.

  public static int Factorial (int N)
  {

  // Computes the factorial of N (N!) recursively
  // Pre : N is defined
  // Post: returns N!

    if (N == 1)
    {
      return 1;                   // stopping case
    }
    else
    {
      return N * Factorial(N-1);  // recursion
    }
  }

and a program that illustrates the function:

//--------------------------------------------------------------
//| TestFactorial.java
//| Illustrates recursive Factorial algorithm
//| Author: M.B. Feldman, The George Washington University
//| Last Modified: March 2003
//--------------------------------------------------------------
import cs1.Keyboard;
public class TestFactorial
{

  public static int Factorial (int N)
  {

  // Computes the factorial of N (N!) recursively
  // Pre : N is defined
  // Post: returns N!

    if (N == 1)
    {
      return 1;                   // stopping case
    }
    else
    {
      return N * Factorial(N-1);  // recursion
    }
  }

  public static void main (String[] args)
  {

    System.out.println("  N\tN!");
    System.out.println();

    for (int Num = 1; Num <= 20; Num++)
    {
      System.out.println(Num + "\t" + Factorial(Num));
    }

  }
}

When this program is run it produces the following output:

1       1
2       2
3       6
4       24
5       120
6       720
7       5040
8       40320
9       362880
10      3628800
11      39916800
12      479001600
13      1932053504
14      1278945280
15      2004310016
16      2004189184
17      -288522240
18      -898433024
19      109641728
20      -2102132736

Note that the values above 13! are unpredictable - this is because the computation has overflowed the limits of the 32-bit integer representation in the computer. If you really wanted to compute large factorials, you could use long values instead of int ones; this would give you a 64-bit representation.

Fibonacci Numbers

A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive?

The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34,... increases rapidly: Each number in the sequence is the sum of the two previous ones. The fifteenth number in the sequence is 610 (that’s a lot of rabbits). The Fibonacci sequence is defined below.

• Fib₁ is 1.
• Fib₂ is 1.
• Fib_n is Fib_n-2 + Fib_n-1, for n > 2.

  public static int Fibonacci (int N)
  {

    // Returns the Nth Fibonacci number, computed recursively
    // Pre : N is defined and N >= 0
    // Post: returns N!

    if ((N == 1) || (N == 2))
    {
      return 1;
    }
    else
    {
      return Fibonacci(N-2) + Fibonacci(N-1);
    }
  }
 

Greatest Common Divisor

• GCD(M, N) is N if N <= M and N divides M.
• GCD(M, N) is GCD(N, M) if M < N.
• GCD(M, N) is GCD(N, remainder of M divided by N) otherwise.

//--------------------------------------------------------------
//| TestGCD.java
//| Illustrates recursive GCD algorithm
//| Author: M.B. Feldman, The George Washington University
//| Last Modified: March 2003
//--------------------------------------------------------------
import cs1.Keyboard;
public class TestGCD
{

  public static int GCD (int M, int N)
  {
    // Pre : M and N are defined and >= 0
    // Post: Returns the greatest common divisor of M and N.

    int Result;

    if ((N <= M) && (M % N == 0))
    {
      Result = N;                  // stopping case
    }
    else if (M < N)
    {
      Result = GCD(N, M);          // recursion
    }
    else
    {
      Result = GCD(N, M % N);    // recursion
    }
    return Result;
  }

  public static void main (String[] args)
  {

    System.out.print("Please enter two positive integers. > ");
    int Num1 = Keyboard.readInt();
    int Num2 = Keyboard.readInt();

    System.out.println("Their greatest common divisor is " +
                       GCD(Num1, Num2));
  }
}
 

Reversal of a String

One way to discover whether a phrase, or string of characters, is a palindrome, is to find the reverse of the string. The string is a palindrome if its reverse is identical to it.

We can find the reverse of a string very easily using the following algorithm:

To find the reverse of a string:

1. If the string contains only one character, its reverse is identical to it and we’re finished.
2. Otherwise, save the first character.
3. Find the reverse of the remaining string, then concatenate the saved character onto the right-hand end.

It is important to realize that step 1 and step 3 are very different in kind from one another. Step 1 is a terminating condition, sometimes called a stopping case or a trivial case. It is a step that can be carried out without making a further recursive call. Step 3, on the other hand, requires the recursive call “find the reverse.” Every recursive algorithm must have at least one terminating condition, otherwise, the algorithm has no way to stop and will, in theory, execute an infinte number of recursive calls. In practice, because every subprogram uses some memory when it is called, a recursive subprogram that never reaches a terminating condition will exhaust the memory available to it and terminate in that graceless fashion.

Here is a Java function that will find the reverse of a string:

   //-----------------------------------------------------------------
   //  Finds reverse of a string, recursively
   //-----------------------------------------------------------------
   public static String reverse (String S)
   {
     System.out.println("Now examining " + S);
     if (S.length() <= 1)
     {
       return S;                                     // stopping case
     }
     else
     {
       return reverse(S.substring(1)) + S.charAt(0); // recursion
     }
   }

and a program that tests whether an input string is a palindrome:

//********************************************************************
//  TestPalindrome.java       M. Feldman, derived from Lewis/Loftus
//
//  Demonstrates the use of recursive string reverse method
//********************************************************************

import cs1.Keyboard;

public class TestPalindrome
{
   //-----------------------------------------------------------------
   //  Finds reverse of a string, recursively
   //-----------------------------------------------------------------
   public static String reverse (String S)
   {
     System.out.println("Now examining " + S);
     if (S.length() <= 1)
     {
       return S;                                     // stopping case
     }
     else
     {
       return reverse(S.substring(1)) + S.charAt(0); // recursion
     }
   }
   //-----------------------------------------------------------------
   //  Tests strings to see if they are palindromes.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      String str, rev, another = "y";

      while (another.equalsIgnoreCase("y")) // allows y or Y
      {
         System.out.print ("Enter a potential palindrome: ");
         str = Keyboard.readString();

         rev = reverse(str);

         System.out.println("Its reverse is " + rev);

         if (rev.equals(str))
         {
            System.out.println ("That string IS a palindrome.");
         }
         else
         {
            System.out.println ("That string IS NOT a palindrome.");
         }

         System.out.println();
         System.out.print ("Test another palindrome (y/n)? ");
         another = Keyboard.readString();
      }
   }
}

This program treats blanks and punctuation marks as ordinary characters and so does not discover that “Madam, I’m Adam” is a palindrome. On the other hand, "madamimadam" will be properly detected. As an exercise, you can improve this program so that blanks and punctuation are ignored, and uppercase letters are treated the same as lowercase ones.
 

Recursive Binary Search

Let’s consider a clever way to look up a friend’s phone number in this long list. (Actually, it’s a way better suited to a computer than to a person, but that’s because people often “look things up” intuitively instead of using algorithms!)

To look up a name:

1. Divide your list in half.
2. Find the name right in the middle of the list. (If the number of names is even, choose the one just below the middle.) If this name is the one whose number you’re searching for, you’re fnished.
3. If your friend’s name is earlier in the alphabet than the middle one, ignore all the names from this middle one to the end, and look up the name only in the first half. Divide this shorter list in half, then look at its middle element, and so on.
4. If your friend’s name is later in the alphabet than the middle one, ignore the first half of the list and look up the name in the second half, as above.

Like the reversal and permutation algorithms, this method is recursive: the same method applied to the full list is applied to half the list, then to half of the half, etc.

Here is a Java function for recursive binary search. This one is simplified so it searches an array of integers rather than one of strings; it would be straightforward to enhance it so that it could search an array or strings or any other comparable objects.

// Main, Fig. 11.2, p. 554
public static int search (int[] a, int first, int size, int target)
{
  int middle;

  if (size <= 0)
    return -1;
  else
  {
    middle = first + size/2;
    if (target == a[middle])
      return middle;
    else if (target < a[middle])
      // the target is less than a[middle], so search before the middle
      return search(a, first, size/2, target);
    else
      // the target must be greater than a[middle], so search after the middle
      return search(a, middle+1, (size-1)/2, target);
  }
}

(end of article)