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 Function

 A type of formula to create a recursive function is:

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

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

  • In its body, the function must call itself
  • Before or after calling itself, the function 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 function 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 function, we will display the current value of the argument, subtract 2, and recall the function itself. Here is our function:

using namespace System;

void OddNumbers(int a)
{
    if( a >= 1 )
    {
	Console::Write(L"{0}, ", a);
	a -= 2;
	OddNumbers(a);
    }
}

int main()
{
	const int Number = 9;

	Console::WriteLine(L"Odd Numbers");
	OddNumbers(Number);

	Console::WriteLine();
	return 0;
}

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

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

Using Recursive Functions

Recursive functions 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 function 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 function can be implemented as follows:

using namespace System;

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

void OddNumbers(int a)
{
    if( a >= 1 )
    {
	Console::Write(L"{0}, ", a);
	a -= 2;
	OddNumbers(a);
    }
}

int main()
{
	const int Number = 9;

	Console::WriteLine(L"Odd Numbers");
	OddNumbers(Number);

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

	Console::WriteLine();
	return 0;
}

This would produce:

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

Press any key to continue . . .

 

 

Previous Copyright © 2006-2016, FunctionX, Inc. Next