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 |

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.

- 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)Figure 1 illustrates what we mean by this. Let's assume that for a particular problem of size

{

Solve it

}

else

{

Reduce the problem using recursion

}

**Figure 1**

**Splitting a Problem into Smaller 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`

`//| 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();`

` }`

` }`

`}`

To find N!:

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

= 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`

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

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.

- Fib
_{1}is 1. - Fib
_{2}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);`

` }`

` }`

- 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));`

` }`

`}`

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:

- If the string contains only one character, its reverse is identical to it and we’re finished.
- Otherwise, save the first character.
- 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.

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:

- Divide your list in half.
- 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.
- 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.
- 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)