Pending Method Instances of the Same Method

---

While MethodC was being executed in the program of Listing 23.1, each of the methods Main, MethodA, and MethodB had exactly one associated pending method instance. It also is possible for one single method to have many associated pending method instances in C#. This ability is one of the fundamental requirements for writing recursive methods in a particular computer language. To demonstrate this ability, let's look at Listing 23.2 that generates four pending method instances similar to those in Listing 23.1, but this time the pending method instances (apart from Main) are all of the same method. It is our aim with the single method in Listing 23.2 to get as close as possible to the functionality of Listing 23.1.

Listing 23.2 SimpleRecursion.cs

01: using System; 02: 03: class TestRecursive 04: { 05:     public static void Main() 06:     { 07:         Recurs(3); 08:     } 09: 10:     public static void Recurs(int level) 11:     { 12:         Console.WriteLine("First part of Recurs. Level: { 0} ", level); 13: 14:         if (level == 1) 15:             return; 16:         else 17:             Recurs(level - 1); 18: 19:         Console.WriteLine("Last part of Recurs.  Level: { 0} ", level); 20:     } 21: } First part of Recurs. Level: 3 First part of Recurs. Level: 2 First part of Recurs. Level: 1 Last part of Recurs.  Level: 2 Last part of Recurs.  Level: 3 

Instead of the three methods (MethodA, MethodB and MethodC) in Listing 23.1, this listing contains a single method Recurs (lines 10 20). To get the same chain of calls as those in Listing 23.1, we must make Recurs act like MethodA and MethodB when level is equal to 3 and 2, and make Recurs act like MethodC when level is equal to 1. This is achieved with the if statement in lines 14 17. If level is equal to 1, the method simply returns (line 15) as MethodC; if level is different from 1 (as when level is equal to 2 or 3), the method makes another method call with the argument (level-1) (as MethodA and MethodB). In this case, the call is made to Recurs itself, which makes Recurs a recursive method. However, because one method can have numerous pending method instances, we can trace the program in a very similar fashion to that in Listing 23.1, which is illustrated in Figure 23.2. In line 7, Main calls Recurs and passes it the argument 3. Thus, level is equal to 3 in the first method instance of Recurs, as illustrated in Figure 23.2. Because level is different from 1 in line 14, line 17 is executed, which is a call to Recurs with the argument 2 (level-1 = 3 - 1). Another method instance of Recurs is generated, and we have one pending Recurs method with level equal to 3. In the new Recurs instance, level is equal to 2, so line 17 is executed again, this time passing along the argument 1 (2-1). In the new method instance, which corresponds to the lowest rectangle in Figure 23.2, level is equal to 1, so this time line 15 is executed (acting like MethodC). Control is returned to the previous pending Recurs method instance, which executes its last WriteLine statement before returning control to the previous method instance, which finally returns control to the Main method where the program is terminated.

Figure 23.2. Recurs's three method instances.

Recurs does not repeatedly call itself infinitely many times because every time Recurs calls itself, the new generated method instance contains a level value that is closer to the value 1 than the previous method instance that (due to line 14) will stop the chain of calls with a return statement (line 15) instead of another method call (line 17).

The following method called RecursCountUp is somewhat similar to Recurs, but with a couple interesting differences. The if condition is true when level is equal to 10, instead of equal to 1, and every time RecursCountUp calls itself, it provides the argument (level + 1) instead of (level-1). Thus, if our initial call to RecursCountUp contains the argument 1, new method instances of RecursCountUp will be created with level values gradually increasing until 10 is reached, at which time the return statement is executed causing all pending RecursCountUp methods to be closed one by one.

If you want to run the RecursCountUp method, you simply can insert it into Listing 23.2 instead of the Recurs method, and substitute the call Recurs(3) in the Main method with RecursCountUp(1).

 public static void RecursCountUp (int level) {     Console.WriteLine("First part of Recurs. Level: { 0} ", level);     if (level == 10)         return;     else         RecursCountUp(level + 1);     Console.WriteLine("Last part of Recurs.  Level: { 0} ", level); } 

The value, which causes the return statement to be called, (1 in Recurs and 10 in RecursCountUp) is called the base case. The call to the method itself ((Recurs (level-1) or RecursCountUp (level + 1) ) is called the recursive call or the recursive step. To avoid an infinite number of calls, the recursive call in a recursive method must give rise to a new method instance that is closer to the base case. For example, (level-1) made level closer to 1 in the next method instance of Recurs, and (level + 1) made level closer to 10 in the next method instance of RecursCountUp. There are many different variations on this theme; in the following sections, we present just a couple of them..

---