Recursion

In C#, a method can call itself. This process is called recursion, and a method that calls itself is said to be recursive. In general, recursion is the process of defining something in terms of itself and is somewhat similar to a circular definition. The key component of a recursive method is that it contains a statement that executes a call to itself. Recursion is a powerful control mechanism.

The classic example of recursion is the computation of the factorial of a number. The factorial of a number N is the product of all the whole numbers between 1 and N. For example, 3 factorial is 1×2×3, or 6. The following program shows a recursive way to compute the factorial of a number. For comparison purposes, a nonrecursive equivalent is also included.

 // A simple example of recursion. using System; class Factorial {   // This is a recursive function.   public int factR(int n) {     int result;     if(n==1) return 1;     result = factR(n-1) * n;     return result;   }   // This is an iterative equivalent.   public int factI(int n) {     int t, result;     result = 1;     for(t=1; t <= n; t++) result *= t;     return result;   } } class Recursion {   public static void Main() {     Factorial f = new Factorial();     Console.WriteLine("Factorials using recursive method.");     Console.WriteLine("Factorial of 3 is " + f.factR(3));     Console.WriteLine("Factorial of 4 is " + f.factR(4));     Console.WriteLine("Factorial of 5 is " + f.factR(5));     Console.WriteLine();     Console.WriteLine("Factorials using iterative method.");     Console.WriteLine("Factorial of 3 is " + f.factI(3));     Console.WriteLine("Factorial of 4 is " + f.factI(4));     Console.WriteLine("Factorial of 5 is " + f.factI(5));   } }

The output from this program is shown here:

 Factorials using recursive method. Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120 Factorials using iterative method. Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120

The operation of the nonrecursive method factI( ) should be clear. It uses a loop starting at 1 and progressively multiplies each number by the moving product.

The operation of the recursive factR( ) is a bit more complex. When factR( ) is called with an argument of 1, the method returns 1; otherwise, it returns the product of factR(n−1)*n. To evaluate this expression, factR( ) is called with n−1. This process repeats until n equals 1 and the calls to the method begin returning. For example, when the factorial of 2 is calculated, the first call to factR( ) will cause a second call to be made with an argument of 1. This call will return 1, which is then multiplied by 2 (the original value of n). The answer is then 2. You might find it interesting to insert WriteLine( ) statements into factR( ) that show at what level each call is and what the intermediate results are.

When a method calls itself, new local variables and parameters are allocated storage on the system stack, and the method code is executed with these new variables from the start. (A recursive call does not make a new copy of the method.) As each recursive call returns, the old local variables and parameters are removed from the stack, and execution resumes at the point of the call inside the method. Recursive methods could be said to “telescope” out and back.

Here is another example of recursion. The displayRev( ) method uses recursion to display its string argument backwards.

 // Display a string in reverse by using recursion. using System; class RevStr {   // Display a string backwards.   public void displayRev(string str) {     if(str.Length > 0)       displayRev(str.Substring(1, str.Length-1));     else       return;     Console.Write(str[0]);   } } class RevStrDemo {   public static void Main() {     string s = "this is a test";     RevStr rsOb = new RevStr();     Console.WriteLine("Original string: " + s);     Console.Write("Reversed string: ");     rsOb.displayRev(s);     Console.WriteLine();   } }

Here is the output:

 Original string: this is a test Reversed string: tset a si siht

Each time displayRev( ) is called, it first checks to see if str has a length greater than zero. If it does, it recursively calls displayRev( ) with a new string that consists of str minus its first character. This process repeats until a zero-length string is passed. This causes the recursive calls to start unraveling. As they do, the first character of str in each call is displayed. This results in the string being displayed in reverse order.

Recursive versions of many routines may execute a bit more slowly than the iterative equivalent because of the added overhead of the additional method calls. Too many recursive calls to a method could cause a stack overrun. Because storage for parameters and local variables is on the system stack, and each new call creates a new copy of these variables, it is possible that the stack could be exhausted. If this occurs, the C# runtime system will cause an exception. However, you probably will not have to worry about this unless a recursive routine runs wild.

The main advantage to recursion is that some types of algorithms can be more clearly and simply implemented recursively than iteratively. For example, the QuickSort sorting algorithm is quite difficult to implement in an iterative way. Also, some problems, especially AI-related ones, seem to lend themselves to recursive solutions.

When writing recursive methods, you must have a conditional statement, such as an if, somewhere to force the method to return without the recursive call being executed. If you don’t do this, once you call the method, it will never return. This type of error is very common when working with recursion. Use WriteLine( ) statements liberally so that you can watch what is going on and abort execution if you see that you have made a mistake.