
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

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.

Application:
Introducing Recursion


 To start a new application, on the main menu, click File > New
Project...
 In the middle list, click Empty Project
 Change the nema to Recursions and press Enter
 In the Solution Explorer, rightclick Recursions > Add > New Item
 In the middle list, click Code File
 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 . . .
Application:
Creating a Recursive Method


 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;
}
}
 Execute the application to test it
 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 . . .
 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 . . .
Application:
Using Recursive Methods


 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;
}
}
 Execute the application to test it
 When asked to provide a number, type 20 and press
Enter
 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
 Press Enter to close the DOS window
 On the main menu, click File > Close Solution
 When asked whether you want to save, click No

