Click here to Skip to main content
11,436,156 members (60,966 online)
Click here to Skip to main content

Recursive methods using C#

, 23 Apr 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
For beginners, Recursive introduction, Examples, Benefits and Defects. A part of Data structure.

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:

  1. Recursive method calls itself so many times until being satisfied.
  2. 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)//The condition that limites the method for calling itself
        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 F0 = 0 and F1= 1 then:

Fn = Fn-1 + Fn-2

The following code is a method to compute Fn (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)//satisfaction condition
        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)//Condition for limiting
    return ex;
return GetInnerException(ex.InnerException);//Calling the method with inner exception parameter

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))//Gets all files in the current path
      {
          result.Add(fileName);
      }

      foreach (string directory in Directory.GetDirectories(path))//Gets all folders in the current path
      {
         SearchForFiles(directory);//The methods calls itself with a new parameter, here!
      }
   }
   catch (System.Exception ex)
   {
      errors.Add(path, ex.Message);//Stores Error Messages in a dictionary with path in key
   }
}

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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shahin Khorshidnia
Software Developer (Senior)
Iran (Islamic Republic Of) Iran (Islamic Republic Of)
Microsoft Certified Technology Specialist (MCTS)


"شاهین خورشیدنیا"
Follow on   LinkedIn

Comments and Discussions

 
GeneralA tidbit of nice chocolate 5/5 Pin
Frank Reidar Haugen13-Feb-14 10:51
memberFrank Reidar Haugen13-Feb-14 10:51 
GeneralMy vote of 2 Pin
Jason Curl28-Apr-13 3:21
professionalJason Curl28-Apr-13 3:21 
GeneralMy vote of 2 Pin
Cindy Meister24-Apr-13 7:40
memberCindy Meister24-Apr-13 7:40 
GeneralThank you. Pin
Shahin Khorshidnia24-Apr-13 9:51
memberShahin Khorshidnia24-Apr-13 9:51 
Question[My vote of 1] Not this crap again. Pin
FatCatProgrammer24-Apr-13 5:02
memberFatCatProgrammer24-Apr-13 5:02 
AnswerThank you. Pin
Shahin Khorshidnia24-Apr-13 9:53
memberShahin Khorshidnia24-Apr-13 9:53 
AnswerRe: [My vote of 1] Not this crap again. Pin
SteveQ5629-Apr-13 8:14
memberSteveQ5629-Apr-13 8:14 
GeneralThanks Pin
Shahin Khorshidnia29-Apr-13 9:42
memberShahin Khorshidnia29-Apr-13 9:42 
QuestionStackoverflowException Pin
thefiloe23-Apr-13 10:14
memberthefiloe23-Apr-13 10:14 
AnswerRe: StackoverflowException Pin
Shahin Khorshidnia23-Apr-13 10:24
memberShahin Khorshidnia23-Apr-13 10:24 
GeneralMy vote of 2 Pin
jfriedman23-Apr-13 10:12
professionaljfriedman23-Apr-13 10:12 
GeneralThanks Pin
Shahin Khorshidnia23-Apr-13 10:25
memberShahin Khorshidnia23-Apr-13 10:25 
GeneralMy vote of 5 Pin
VitorHugoGarcia26-Feb-13 23:42
memberVitorHugoGarcia26-Feb-13 23:42 
GeneralRe: My vote of 5 Pin
Shahin Khorshidnia27-Feb-13 1:15
memberShahin Khorshidnia27-Feb-13 1:15 
GeneralRe: My vote of 5 Pin
VitorHugoGarcia27-Feb-13 1:33
memberVitorHugoGarcia27-Feb-13 1:33 
GeneralMy vote of 3 Pin
Vitaly Tomilov21-May-12 9:59
memberVitaly Tomilov21-May-12 9:59 
GeneralThank you Pin
Shahin Khorshidnia15-Jul-12 0:15
memberShahin Khorshidnia15-Jul-12 0:15 
GeneralRe: Thank you Pin
_groo_23-Apr-13 2:20
member_groo_23-Apr-13 2:20 
GeneralRe: Thank you Pin
Shahin Khorshidnia23-Apr-13 9:16
memberShahin Khorshidnia23-Apr-13 9:16 
GeneralMy vote of 2 Pin
Jasmine250115-May-12 7:49
memberJasmine250115-May-12 7:49 
GeneralRe: My vote of 2 [modified] Pin
Shahin Khorshidnia15-May-12 8:20
memberShahin Khorshidnia15-May-12 8:20 
GeneralRe: My vote of 2 Pin
Jasmine250116-May-12 7:11
memberJasmine250116-May-12 7:11 
GeneralRe: My vote of 2 Pin
Jasmine250116-May-12 7:14
memberJasmine250116-May-12 7:14 
GeneralThanks Pin
Shahin Khorshidnia16-May-12 8:58
memberShahin Khorshidnia16-May-12 8:58 
AnswerRe: Thanks Pin
Clifford Nelson23-Apr-13 9:33
memberClifford Nelson23-Apr-13 9:33 
GeneralRe: My vote of 2 Pin
Shahin Khorshidnia23-Apr-13 9:41
memberShahin Khorshidnia23-Apr-13 9:41 
QuestionIs Linq better? Pin
George Swan7-May-12 22:34
memberGeorge Swan7-May-12 22:34 
AnswerRe: Is Linq better? Pin
Shahin Khorshidnia7-May-12 23:55
memberShahin Khorshidnia7-May-12 23:55 
GeneralRe: Is Linq better? Pin
George Swan8-May-12 1:00
memberGeorge Swan8-May-12 1:00 
GeneralRe: Is Linq better? Pin
Robert Rohde8-May-12 4:49
memberRobert Rohde8-May-12 4:49 
GeneralRe: Is Linq better? [modified] Pin
Shahin Khorshidnia8-May-12 5:17
memberShahin Khorshidnia8-May-12 5:17 
QuestionImages Missing Pin
clintonG7-May-12 10:41
memberclintonG7-May-12 10:41 
AnswerRe: Images Missing Pin
Shahin Khorshidnia7-May-12 10:54
memberShahin Khorshidnia7-May-12 10:54 
AnswerRe: Images Missing Pin
Shahin Khorshidnia8-May-12 6:31
memberShahin Khorshidnia8-May-12 6:31 
GeneralRe: Images Missing Pin
clintonG8-May-12 11:24
memberclintonG8-May-12 11:24 
GeneralYW Pin
Shahin Khorshidnia8-May-12 12:04
memberShahin Khorshidnia8-May-12 12:04 
You're welcome Smile | :)
Do not criticise, if you don't have any better idea.

GeneralMy vote of 5 Pin
Аslam Iqbal2-May-12 4:15
memberАslam Iqbal2-May-12 4:15 
GeneralRe: My vote of 5 Pin
Shahin Khorshidnia2-May-12 4:44
memberShahin Khorshidnia2-May-12 4:44 
Question[My vote of 1] Not great. Pin
PHS2411-May-12 0:32
memberPHS2411-May-12 0:32 
AnswerThanks Pin
Shahin Khorshidnia1-May-12 1:01
memberShahin Khorshidnia1-May-12 1:01 
Question[My vote of 1] not great Pin
CIDev27-Apr-12 7:46
memberCIDev27-Apr-12 7:46 
AnswerThank you [modified] Pin
Shahin Khorshidnia27-Apr-12 7:54
memberShahin Khorshidnia27-Apr-12 7:54 
AnswerArticle updated Pin
Shahin Khorshidnia1-May-12 0:01
memberShahin Khorshidnia1-May-12 0:01 
GeneralRe: Article updated Pin
CIDev1-May-12 5:00
memberCIDev1-May-12 5:00 
GeneralThank you Pin
Shahin Khorshidnia1-May-12 5:15
memberShahin Khorshidnia1-May-12 5:15 
GeneralMy vote of 3 Pin
Manfred R. Bihy3-Jan-12 3:03
memberManfred R. Bihy3-Jan-12 3:03 
GeneralRe: My vote of 3 Pin
Shahin Khorshidnia6-Feb-12 10:04
memberShahin Khorshidnia6-Feb-12 10:04 
GeneralArticle updated Pin
Shahin Khorshidnia1-May-12 0:04
memberShahin Khorshidnia1-May-12 0:04 
GeneralRe: Article updated Pin
Manfred R. Bihy1-May-12 8:04
mvpManfred R. Bihy1-May-12 8:04 
GeneralRe: Article updated Pin
Shahin Khorshidnia1-May-12 8:38
memberShahin Khorshidnia1-May-12 8:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150428.2 | Last Updated 23 Apr 2013
Article Copyright 2011 by Shahin Khorshidnia
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid