## What is Recursive Function/Method?

A Method can call another methods but it can also call itself. When a mathod calls itself, it'll be named recursive method.

A *Recursive* usuallly, has the two specifications:

- Recursive method calls itself so many times until being satisfied.
- Recursive method has parameter(s) and calls itself with new parameter values.

**So, what is recursive function? **There is no difference between function and method except that functions are not utilizable outside of their classes. In C# we had only method but anonymous function has been added to C#, since .NET Framework 3.5. (more information)

So, it's better to say Recursive method instead of Recursive function and I say *Recursive* in this artcile.

## Why, when and how to use Recursive in our application?

"*Any program that can be written using assignment, the *`if-then-else`

statement and the `while`

statement can also be written using assignment, `if-then-else`

and Recursion". (Fundamentals of Data Structure in C by Ellis Horowitz)

*Recursive* solution is a powerful and simple approach for complicated developments, but it can **worsen performance** because of using call stack again and again (sometimes scandal performance).

Look at the Diagram:

^{Call Stack Diagram}

I'm going to give examples for a better conseption of its risks and rewards:

**1. The Factorial**

We know that the factorial (!) of a positive integer number is the product of all positive integers less than or equal to the number.

0! = 1
1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
...
n! = n * (n - 1)!

The following code is a method to compute the Factorial (no recursive):

public long Factorial(int n)
{
if (n == 0)
return 1;
long value = 1;
for (int i = n; i > 0; i--)
{
value *= i;
}
return value;
}

Computing the Factorial by a recursive method. Shorter and clearer than previous code :

public long Factorial(int n)
{
if (n == 0) return 1;
return n * Factorial(n - 1);
}

You know, the factorial of `n`

is actually the factorial of `(n-1)`

mutiplied by `n`

, if `n `

> 0.

**Or**:

`Factorial(n) returns Factorial(n-1) * n`

That is the returned value of the method; and before that, we need a condition:

`If n = 0 Then Return 1`

I think, the program logic is now clear and we can understand it.

**2. The Fibonacci Numbers**

The Fibonacci numbers are the numbers in the following sequence:

0,1,1,2,3,5,8,13,21,34,55,…

If F_{0} = 0 and F_{1}= 1 then:

F_{n} = F_{n-1} + F_{n-2}

The following code is a method to compute `F`_{n}

(no recursive and high performance):

public long Fib(int n)
{
if (n < 2)
return n;
long[] f = new long[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}

If we use recursive method, our code will be more simple, **but a very poor performance**:

public long Fib(int n)
{
if (n == 0 || n == 1) return n;
return Fib(k - 2) + Fib(k - 1);
}

**3. Boolean Compositions**

Sometimes solving the problem is more complicated than the Fibonacci. For example, we want to show all possible compositions for n Boolean variables. In other words, if `n = 3`

, then we must have the following output:

*true, true, true
true, true, false
true, false, true
true, false, false
false, true, true
false, true, false
false, false, true
false, false, false*

Solving this problem without a recursive function is not so easy and not simple, when we have quantities for `n`

.

public void CompositionBooleans(string result, int counter)
{
if (counter == 0)
return;
bool[] booleans = new bool[2] { true, false };
for (int j = 0; j < 2; j++)
{
StringBuilder stringBuilder = new StringBuilder(result);
stringBuilder.Append(string.Format("{0} ", booleans[j].ToString())).ToString();
if (counter == 1)
Console.WriteLine(stringBuilder.ToString());
CompositionBooleans(stringBuilder.ToString(), counter - 1);
}
}

Now, we can use and call this method:

CompositionBoolean(string.Empty, 3);

For using *Recursive*, Ian Shlasko suggested this:

public void BooleanCompositions(int count)
{
BooleanCompositions(count - 1, "true");
BooleanCompositions(count - 1, "false");
}
private void BooleanCompositions(int counter, string partialOutput)
{
if (counter <= 0)
Console.WriteLine(partialOutput);
else
{
BooleanCompositions(counter - 1, partialOutput+ ", true");
BooleanCompositions(counter - 1, partialOutput+ ", false");
}
}

**4. InnerExceptions**

Recursive methods are useful for getting the last `innerException`

:

public Exception GetInnerException(Exception ex)
{
return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);
}

Why the last `innerException`

?! That's beside the point. The subject of our talk is, if you want to get the last `innerException`

, you can count on Recursive method.

This code:

return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);

is abridgment of and equivalent to the following code:

if (ex.InnerException == null) return ex;
return GetInnerException(ex.InnerException);

Now, when we have an exception, we can find the last `innerException `

of the exception. For example:

try
{
throw new Exception("This is the exception",
new Exception("This is the first inner exception.",
new Exception("This is the last inner exception.")));
}
catch (Exception ex)
{
Console.WriteLine(GetInnerException(ex).Message);
}

I decided to write about Anonymous Recurcive Methods, but I could't explain that better this article.

**5. Find Files**

I used *Recursive* in the sample project that you can download it. It's able to search a path and get all files form the current folder and subfolders.

private Dictionary<string, string> errors = new Dictionary<string, string>();
private List<string> result = new List<string>();
private void SearchForFiles(string path)
{
try
{
foreach (string fileName in Directory.GetFiles(path)) {
result.Add(fileName);
}
foreach (string directory in Directory.GetDirectories(path)) {
SearchForFiles(directory); }
}
catch (System.Exception ex)
{
errors.Add(path, ex.Message); }
}

The method seems not to have any satisfy condition because it will be satisfied in each directory automatically, if it iterates all files and doesn't find any subfolder there.

## Consequently

We can use iterative algorithms instead of recursive and have a better performance but we may also have time expense and *None-Recursive Function*. The point is we have to choose the best approach which depends on situations.

Dr. James McCaffrey believes that don't use Recursive unless necessary. Read his article.

**I prefer to**:

**A)** Avoid using *Recursive* when the performance is a very-very important critical subject.

**B)** Avoid of using *Recursive*, when the iterative is not very "complicated".

**C)** Do not procrastinate about using *Recursive*, if (!A && !B)

For example:

Section 1 (Factorial): The iterative is not complicated then avoid recursion.

Section 2 (Fibonacci): *Recursive* like that is not recommended.

Of course it doesn't reduce the value of *Recursive;* I can remind Minimax algorithm (an important chapter in Artificial Intelligence) that *Recursive* is its all.

But if you decided to use a recursive method, it's better to try optimizing it with Memoization.

Good luck!