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

RECURSIVE ALGORITHMS

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

Problems that lend themselves to a recursive solution have the following characteristics:
• 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.
The recursive algorithms that we write will generally consist of an if statement with the form shown below:
`    if (the stopping case is reached)    {         Solve it    }    else    {        Reduce the problem using recursion    }`
Figure 1 illustrates what we mean by this. Let's assume that for a particular problem of size N, we can split this problem into one involving a problem of size 1, which we can solve (a stopping case), and a problem of size N - 1, which we can split further. If we split the problem N times, we will end up with N problems of size 1, all of which we can solve.

Figure 1
Splitting a Problem into Smaller Problems

Recursive Multiplication

Consider how we might solve the problem of multiplying 6 by 3, assuming that we know the addition tables but not the multiplication tables. The problem of multiplying 6 by 3 can be split into the two problems:

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
//--------------------------------------------------------------
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

A classical simple example of recursion is the definition of the factorial of a positive integer N. Written N! and read “N factorial,” this is easily understood as the product 1 x 2 x . . . x N. Thus, 3! = 6, 4! = 24, 5! = 120, and so on. But we can write a definition without any “dot-dot-dot” as follows:

To find N!:

1. If N = 1 then N!  = 1;
2. Otherwise N! = N x (N - 1)!
We have defined the “!” operation in terms of “!”. Notice that the definition is not circular, because the “!” is applied to a smaller and smaller number each time until it is applied to 1. Here is the definition applied to calculate 5!.

Recursive Calculation of 5!

5! = 5 x 4!
= 5 x (4 x 3!)
= 5 x (4 x (3 x 2!))
= 5 x (4 x (3 x (2 x 1!)))
= 5 x (4 x (3 x (2 x 1)))
= 5 x (4 x (3 x 2))
= 5 x (4 x 6)
= 5 x 24
= 120

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
//--------------------------------------------------------------
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

The Fibonacci numbers are a sequence of numbers that have many varied uses. They were originally intended to model the growth of a rabbit colony. The Italian mathematician Leonardo Pisano (1170-1250), who was known by the nickname Fibonacci, posed this problem:
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?
(See http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Fibonacci.html for details)

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.

• Fib1 is 1.
• Fib2 is 1.
• Fibn is Fibn-2 + Fibn-1, for n > 2.
Verify for yourself that the sequence of numbers shown above is correct. Here is a recursive function that computes the Nth Fibonacci number:

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

The greatest common divisor (GCD) of two positve integers is the largest integer that divides them both. The ancient mathmematician Euclid (Alexandria, Egypt, 325-265 BC) discovered this algorithm for finding the GCD:
• 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.
This algorithm states that the GCD is N if N is the smaller number and N divides M. If M is the smaller number, the GCD determination should be performed with the arguments transposed. If N does not divide M, the answer is obtained by finding the GCD of N and the remainder of M divided by N. Here is the function GCD, included within a test program:

//--------------------------------------------------------------
//| TestGCD.java
//| Illustrates recursive GCD algorithm
//| Author: M.B. Feldman, The George Washington University
//--------------------------------------------------------------
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. > ");

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

Reversal of a String

In our natural languages, there is a certain type of phrase known as a palindrome. This is a phrase that reads the same forwards and backwards. Two examples of English palindromes are “radar” and “Able was I ere I saw Elba.” The phrase “Madam, I’m Adam,” supposedly spoken by the Biblical first man when he met his wife-to-be, Eve, is a palindrome if we neglect case, spaces and punctuation. (Adam, in his first fit of anger, might also have said “Mad am I, Madam.”)

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.
Notice that we’ve found the reverse of a string by saving the first character and finding the reverse of what’s left. This is a recursive algorithm: To carry it out on the whole set of data, we need to carry it out on a smaller set of data.

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: ");

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)? ");
}
}
}

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

Imagine that you’ve written up a list of your friends, placing their names in alphabetical order, together with their telephone numbers. Because you’re very popular, you have many friends and this list is quite long, running over a number of pages.

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.
Eventually, one of two things will happen: you’ll find your friend in the list, or you’ll divide the list in half so many times that only one name will remain and it won’t be the one you wanted! (In case of an even number, no names at all will remain.) This will mean that the friend you were looking for isn’t in your list.

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)