Home

C# Topics: Recursion

     

Introduction

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

 

Notice that, to perform this operation, you consider the highest. Then you subtract 2 to get the previous. Again, you subtract 2 from the number to get the previous. What you are simply doing is to subtract a constant to what you already have and you invent very little. In computer programming, you can solve this type of problem by first writing a function, and then have the function call itself. This is the basis for recursion.

   

ApplicationApplication: Introducing Recursion

  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

Creating a Recursive Method

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

ApplicationApplication: Creating a Recursive Method

  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

Using Recursive Methods

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

ApplicationApplication: Using Recursive Methods

  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
 

Home Copyright © 2010-2011 FunctionX