A method can call itself. This technique is known as recursion. You can address some types of problems with recursive solutions. Recursive methods are often useful when manipulating more complex data structures such as lists and trees.
Methods in C# can be mutually recursive. For example, a situation in which method A can call method B, and method B can call method A, is allowable.
Example of a Recursive Method
The Fibonacci sequence occurs in several situations in mathematics and biology (for example, the reproductive rate and population of rabbits). The nth member of this sequence has the value 1 if n is 1 or 2; otherwise, it is equal to the sum of the preceding two numbers in the sequence. Notice that when n is greater than two the value of the nth member of the sequence is derived from the values of two previous values of the sequence. When the definition of a method refers to the method itself, recursion might be involved.
You can implement the Fibonacci method as follows:
static ulong Fibonacci(ulong n)
{
if (n <= 2)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
Notice that two calls are made to the method from within the method itself. A recursive method must have a terminating condition that ensures that it will return without making further calls. In the case of the Fibonacci method, the test for n <= 2 is the terminating condition
Implementing a Method by Using Recursion
If you read the previous blog we implemented the Factorial method using Output parameters , no we will re-implement it using recursion rather than a loop.
The factorial of a number can be defined recursively as follows: the factorial of zero is 1, and you can find the factorial of any larger integer by multiplying that integer with the factorial of the previous number. In summary:
If n=0, then Factorial(n) = 1; otherwise it is n * Factorial(n-1)
//
// Another way to solve the factorial problem,
// this time as a recursive function
//
public static bool RecursiveFactorial(int n, out int f)
{
bool ok=true;
// Trap negative inputs
if (n<0)
{
f=0;
ok = false;
}
if (n<=1)
f=1;
else
{
try
{
int pf;
ok = RecursiveFactorial(n-1,out pf);
f = n * pf;
}
catch(Exception)
{
// Something went wrong. Set error
// flag and return zero.
f=0;
ok=false;
}
}
return ok;
}
