C# Topics: Recursion

Imagine that you want to count the positive odd numbers from a certain maximum to a certain minimum. For example, to count the odd numbers from 1 to 9, you would use:

9, 7, 5, 3, and 1

1. To start a new application, on the main menu, click File -> New Project...
2. In the middle list, click Empty Project
3. Change the nema to Recursions and press Enter
4. In the Solution Explorer, right-click Recursions -> Add -> New Item
5. In the middle list, click Code File
6. Change the name to Calculator and press Enter

 A type of formula to create a recursive method is:

ReturnValue Function(Arguments, if any)
{
    Optional Action . . .
    Function();
    Optionan Action . . .
}

A recursive method starts with a return value. If it would not return a value, you can define it with void. After its name, the method can take one or more arguments. Most of the time, a recursive method takes at least one argument that it would then modify. In the body of the method, you can take the necessary actions. There are no particular steps to follow when implementing a recursive method but there are two main rules to observe:

• In its body, the method must call itself
• Before or after calling itself, the method must check a condition that would allow it to stop, otherwise, it might run continuously

For our example of counting decrementing odd numbers, you could start by creating a method that takes an integer as argument. To exercise some control on the lowest possible values, we will consider only positive numbers. In the body of the method, we will display the current value of the argument, subtract 2, and recall the method itself. Here is our function:

using System;

public class Exercise
{
    static void OddNumbers(int a)
    {
        if (a >= 1)
        {
            Console.Write("{0}, ", a);
            a -= 2;
            OddNumbers(a);
        }
    }
    
    public static int Main()
    {
        const int number = 9;

        Console.WriteLine("Odd Numbers");
        OddNumbers(number);
        
        Console.WriteLine();
        return 0;
    }
}

Notice that the method calls itself in its body. This would produce:

Odd Numbers
9, 7, 5, 3, 1,
Press any key to continue . . .

1. To create a recursive function, change the document as follows:

   using System;
   
   public class Calculator
   {
       private long Factorial(long number)
       {
           if (number <= 1)
               return 1;
           return number * Factorial(number - 1);
       }
   
       public static int Main()
       {
           long factor = 0;
           Calculator exo = new Calculator();
   
           Console.Write("To calculate a factorial, enter a (small positive) number: ");
           factor = long.Parse(Console.ReadLine());
   
           Console.WriteLine("The factorial of {0} = {1}",
               factor, exo.Factorial(factor));
   
           System.Console.ReadKey();
           return 0;
       }
   }

2. Execute the application to test it
3. When asked to provide a number, type 8 and press Enter:

   To calculate a factorial, enter a (small positive) number: 8
   The factorial of 8 = 40320
   Press any key to continue . . .

4. Press Enter to close the DOS window

Recursive methods provide a valuable mechanism for building lists or series, which are value that are either increment or decrement but follow a pattern. Imagine that, instead of simply displaying odd numbers as we did above, you want to add them incrementally. If you have 1, it would also produce 1. If you have 5, you would like to add 1 to 3, then the result to 5, and so on. This can be illustrated as follows:

                1 = 1

            1 + 3 = 4

        1 + 3 + 5 = 9

    1 + 3 + 5 + 7 = 16

1 + 3 + 5 + 7 + 9 = 25

To perform this operation, you would consider 1. If the number is less than or equal to 1, the method should return 1. Otherwise, add 2 to 1, then add 2 to the new result. Continue this until you get to the value of the argument. The method can be implemented as follows:

using System;

public class Exercise
{
    static int AdditionalOdd(int a)
    {
        if (a <= 1)
            return 1;
        return a + AdditionalOdd(a - 2);
    }

    static void OddNumbers(int a)
    {
        if (a >= 1)
        {
            Console.Write("{0}, ", a);
            a -= 2;
            OddNumbers(a);
        }
    }
    
    public static int Main()
    {
        const int Number = 9;

        Console.WriteLine("Odd Numbers");
        OddNumbers(Number);

        Console.WriteLine();
        Console.WriteLine("Sum of Odds: {0}\n", AdditionalOdd(Number));

        return 0;
    }
}

This would produce:

Odd Numbers
9, 7, 5, 3, 1,
Sum of Odds: 25

Press any key to continue . . .

1. Change the document as follows:

   using System;
   
   public class Calculator
   {
       private long Factorial(long number)
       {
           if (number <= 1)
               return 1;
           return number * Factorial(number - 1);
       }
   
       private long Permutation(long n, long r)
       {
           if (r == 0)
               return 0;
           if (n == 0)
               return 0;
           if ((r >= 0) && (r <= n))
               return Factorial(n) / Factorial(n - r);
           else
               return 0;
       }
   
       private long Combinatorial(long a, long b)
       {
           if (a <= 1)
               return 1;
   
           return Factorial(a) / ((Factorial(b) * Factorial(a - b)));
       }
   
       public static int Main()
       {
           long factor = 0;
           long second = 0;
           Calculator exo = new Calculator();
   
           Console.Write("To calculate a factorial, enter a (small positive) number: ");
           factor = long.Parse(Console.ReadLine());
           Console.Write("To calculate a permutation and the combination, enter a second (small positive) number: ");
           second = long.Parse(Console.ReadLine());
   
           Console.WriteLine("Factorial:   F({0}) = {1}",
               factor, exo.Factorial(factor));
           Console.WriteLine("Permutation: P({0}, {1}) = {2}",
               factor, second, exo.Permutation(factor, second));
           Console.WriteLine("Combination: C({0}, {1}) = {2}",
               factor, second, exo.Combinatorial(factor, second));
   
           System.Console.ReadKey();
           return 0;
       }
   }

2. Execute the application to test it
3. When asked to provide a number, type 20 and press Enter
4. When asked to provide a second number, type 5 and press Enter:

   To calculate a factorial, enter a (small positive) number: 20
   To calculate a permutation and the combination, enter a second (small positive)
    number: 5
   Factorial:   F(20) = 2432902008176640000
   Permutation: P(20, 5) = 1860480
   Combination: C(20, 5) = 15504
   

5. Press Enter to close the DOS window
6. On the main menu, click File -> Close Solution
7. When asked whether you want to save, click No