Home

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.
 

Creating a Recursive Methods

 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;

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

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

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

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

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;

class Program
{
    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);
        }
    }
    
    static void Main()
    {
        const int Number = 9;

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

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

This would produce:

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

Press any key to continue . . .

 
Home Copyright © 2006-2016, FunctionX, Inc.