Recursion in C#

Recursion in C# with Examples

In this article, I am going to discuss Recursion in C# with Examples. Please read our previous article where we discussed Call by Value and Call by Reference in C# Language with Examples. At the end of this article, you will understand the following pointers in detail.

  1. What is Recursion in C#?
  2. What does it mean by Recursive Function in C#?
  3. How does Recursion Work in C#?
  4. How to trace a Recursive Function in C#?
  5. Example to Understand Recursion in C#
  6. What are the advantages of Recursion in C# Language?
  7. What are the disadvantages of Recursion in C# Language?
  8. How to Find the Time Complexity of a Recursive Function in C#?
What is Recursion in C#?

Before understanding Recursion, let us have a look at the below image. Here we have the main function and one more function called function ‘fun’ and that fun function is called by the main function.

What is Recursion in C#?

First, we need to understand how this function call is made and how it works. Here, once the program execution starts, it will start executing the program from the main function. First, it will execute the first statement, then it will execute the second statement and then it will execute the third statement i.e. it will call the fun function. Here, the control will move to the fun function definition and start executing that fun function. Inside the fun function, it will start executing the first statement, then the second, and then the third statement. Once it has finished (once the third statement is executed inside the fun function) the control again comes back to the same line i.e. third line of the main function. If any other operations are present in that line they will execute. Otherwise, it will execute the fourth statement and then the fifth statement, and so on.

What does it mean by any other operations?

Let’s say the fun function is returning something and in the main function, I have written added by 2. So, the returning value from the fun function has to be added by two. So, this addition needs to be done once the function has returned to the main function with some value. Assume that the fun function has a return value of 10. So, 10+2 can be done, only if the fun(10) has returned the value. This is the important point that you should remember for understanding the recursion. For a better understanding, please have a look at the below image.

What does it mean by any other operations?

With this kept in mind, let us proceed and understand what is a recursive function.

What does it mean by Recursive Function in C#?

Function calling itself is called Recursion. Recursion is a process by which a function calls itself repeatedly until some specified condition has been satisfied.

In order to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second, the problem statement must include a stopping condition. If a recursive function contains local variables, a different set of local variables will be created during each call. The variables will represent a different set of values each time the function is executed. Each set of values will be stored on the stack. The general form of recursion is given below.

What does it mean by Recursive Function in C#?

This is a recursive function i.e. a function is calling itself. Inside the function body, if you see it is calling itself again, then it is a recursive function.

One important point that you need to remember is that inside a recursive function, you can see that there is a base condition. So, there must be some base condition that will terminate the recursion. There must be some ways to terminate the recursion otherwise it will go into infinite calling. First, we need to call the function the first time, then it will call itself repeatedly again and again. So, there must be some condition under which it must stop.

In this example, the function will call itself as long as the base condition is true or it can stop if the base condition is true. Here if the condition becomes false it will not call further and it stops. So, let us take some examples of the recursive function and study how it works.

How does Recursion Work in C#?

Let us look at an example to understand how recursion works. Please have a look at the following code. Here, we have the main function which is having some value in the variable x, and calling function fun1 passing that variable X value. The function fun1 that takes parameter ‘n’ will accept the x value and if the condition is ‘true, it is printing and then calling itself. So, it’s printing and again calling itself for a reduced value of n.

using System;
namespace RecursionDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 3;
            fun1(x);
            Console.ReadKey();
        }

        static void fun1(int n)
        {
            if (n > 0)
            {
                Console.Write($"{n} ");
                fun1(n - 1);
            }
        }
    }
}

In the above example, we are passing 3 to the fun1 function from the main function. Let us see what will be the result and how it works? Let’s, trace this recursive function and check.

How to trace a Recursive Function in C#?

A recursive function is traced in the form of a tree. So, let us start tracing the above example. When the condition is true inside the fun1 function there are two statements to be executed. In the first statement, it will print the n value and in the second statement it will call itself passing (n-1) and this has to be done only when n is greater than 0.

How to trace a Recursive Function in C#?

Let’s start tracing, from the main function, we are calling function fun1 passing X i.e. value 3. So, the first time it has got 3, and 3 is greater than 0 and hence the condition becomes true. So, the first step is to print ‘n’ i.e. it will print 3 and the second step is to call itself again fun1 for 3-1 i.e. 2. Here, the fun1(3) call has not been completed. It calling itself again.

How does Recursion Work in C#?

So, it will call itself again passing fun1(2). So, let us execute fun1(2), again it will start, 2 is greater than ‘0’ and hence the condition becomes true. So, the first step is to print 2 and then call itself again bypassing fun1(1). Now, the fun1(2) call has not finished, it has printed 2 and it has to call fun1(1).

How does Recursive Function Work in C#?

So again, a new call, a fresh call, that fresh call is fun1(1). 1 is greater than 0, so we have to perform the two steps. The first step is to print 1 and then call itself by passing fun1(0). Now, the fun1(1) call has not finished, it has printed 1 and it has to call fun1(0).

How does Recursive Function Work in C#?

Now, fun1(0), 0 is greater than 0, no it’s not greater than 0. So, it will not enter inside, it will not perform those two steps and it does nothing. So, no printing and no calling and it will not enter inside and it will come outside of the function. So, the fun1(0) call doesn’t do anything. So, it will go back to the previous function call and so on and finally come out from the fun1 to the main function where it is initially called. So, a recursive function forms a tree and this is called the tracing tree of a recursive function. Now we will take one more example.

Example to Understand Recursion in C#:

Let us understand Recursion in C# with an example. Please have a look at the below example which is also an example of the recursive function in C#.

using System;
namespace RecursionDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 3;
            fun2(x);
            Console.ReadKey();
        }

        static void fun2(int n)
        {
            if (n > 0)
            {
                fun2(n - 1);
                Console.Write($"{n} ");
            }
        }
    }
}

The above example is very similar to the first example. Let me compare both the example and show you the difference.

Example to Understand Recursion in C#

If you look at the main function of both the example, they are having one variable called x and calling one function (Example1 calling fun1 function and Example2 calling fun2 function) passing that x value.

The difference in both the example is that in example 1, inside the fun1 function if the condition is true (i.e. n > 0), first it is printing the n value and then calls itself but in example 2, inside the fun2 function if the condition is true (i.e. n > 0), first it is calling itself, and then printing the n value, then what will be the output. Let’s trace example 2 and find out the output.

The program execution will start from the main function. The main function calls the function fun2 by passing value 3 i.e. fun2(3). Inside the fun2 function, first, it will check whether n > 0 and here, n is 3, so 3 is greater than 0 and the condition is satisfied. The first statement within the if block is executed i.e. it calls the fun2 function by passing n-1 i.e. 2. What about the second statement i.e. printing? It will not be executed at this point in time. The point that you need to remember is first the first statement has to be finished in order to execute the second statement i.e. printing. For a better understanding please have a look at the below image.

Example to Understand Recursion in C#

Let us take the fun2(2) call, with n=2, the condition again satisfied as 2 is greater than 0. Again, two steps, first it will call fun2 with n-1 i.e. it will call itself for fun2(1) and the second statement will not be executed at this point. Once the first statement is finished, the second statement will execute. At this point, the tracing tree will be like below.

Example to Understand Recursion in C#

Let us trace fun2(1). Again 1 is greater than 0 and hence the condition is satisfied and again two steps. In the first step, it will call itself bypassing n-1 i.e. fun2(0), and similarly, the second statement will only execute once the first statement completes its execution. So, at this point, the tracing tree of this recursive function is like the one below.

Example to Understand Recursive Function in C#

The next call is fun2(0). Now fun2(0), 0 is greater than 0, no. So, it will not enter inside this ‘if’ block and it will come out i.e. it does nothing. So, this call with parameter 0 has terminated.

Example to Understand Recursive Function in C#

Now once this call has been terminated the control should go back to the previous call. The previous call was fun2(1), it will go back to the function call and execute the next statement i.e. the second statement which is nothing but to print the n value. At this call, the n value is 1 and hence it will print 1. For a better understanding, please have a look at the below image.

Example to Understand Recursive Functions in C#

Then it will go back to the previous call i.e. fun2(2), and the second thing that is remaining here is printing, so the value 2 is printed then it will come out of this function and finish. For better understanding, please have a look at the following image.

Example to Understand Recursive Functions in C#

Once the fun2(2) call finishes, it goes back to the previous call i.e. fun2(3), and the second thing that is remaining here is printing, so the value 3 is printed. And the output you will get from this function is 1 2 3 as shown in the below image.

Recursive Functions in C#

The output of example 1 was 3, 2, 1 and the output of example 2 is 1, 2, 3.

Now, let us compare both of the examples, in example 1, first, the printing was done and then the recursive call was made but in example 2, first the recursive call was made and then the printing was done at returning time.

Note: The most important thing that you need to understand in recursion is that recursion has two phases. One is the calling phase and the other one is returning phase.

Recursion Example in C#: Calculate factorial of a Number

In the below example, we declare our recursive factorial function which takes an integer parameter and returns the factorial of this parameter. This function will call itself and decrease the number until the exiting, or the base condition is reached. When the condition is true, the previously generated values will be multiplied by each other, and the final factorial value is returned. We declare and initialize an integer variable with the value “6” and then print its factorial value by calling our factorial function.

using System;
namespace RecursionDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 6;
            Console.WriteLine($"The factorial of {x} is {factorial(x)}");
            Console.ReadKey();
        }

        static int factorial(int number)
        {
            if (number == 1)
                return (1); /* exiting condition */
            else
                return (number * factorial(number - 1));
        }
    }
}

Output: The factorial of 6 is 720

What are the advantages of Recursion in C# Language?
  1. Function calling-related information will be maintained by recursion.
  2. Stack evaluation will take place by using recursion.
  3. Prefix, postfix, infix notation will be evaluated by using recursion
What are the disadvantages of Recursion in C# Language?
  1. It is a very slow process due to stack overlapping.
  2. The recursive program can create stack overflow.
  3. The recursive program can create infinite loops.
How to Find the Time Complexity of a Recursive Function in C#?

Let us first understand the basic concept for finding the time complexity. We assume that every statement in our program takes one unit of time for execution.

Let me give the idea behind that one. Suppose, there are some books kept in one place and you have to move the book and keep it on a shelf or in a rack. How much time does it take? Maybe half a second, a quarter of a second, maybe if somebody works very slowly may take one second for keeping one book there. The time varies from person to person. So, we don’t mention seconds or milliseconds, we say one unit of time. If you take the example of currency, one dollar, one rupee, and one pound. We say one but what is the market value that might be different. So, we say one buck or one unit of currency.

In the same way, we assume that every statement takes one unit of time. If that statement is repeated multiple times, then we need to count the frequency that how many times it is executed. That is sufficient for analyzing our function.

Example to Find the Time Complexity of a Recursive Function in C#:

We are going to use the following recursive function to calculate the time complexity.

Example to Find the Time Complexity of a Recursive Function in C#

Now, let us see what the above function (fun1) is doing. It is doing nothing just printing. It is just printing the value of n.

How much time does it take for printing? It takes one unit of time for printing.

How many times the Console.Write() function is written there? Only one-time Console.Write() is written there. But this is a recursive function. So, it is calling itself again and again. As it is a recursive function, let us find out how many times the Console.Write() function is executed. As we already discussed, we can find out this using the tracing tree or the recursion tree.

How to Find the Time Complexity of a Recursive Function in C#?

As you can see in the above tracing tree, first it prints the value 3, then print 2 and then print the value 1. That means the Console.Write() statement is executed three times. So, this recursive function will take 3 units of time to execute when the n value is 3. If we make the n value to 5 then it will take 5 units of time to execute this recursive function.

So, we can say for n it will take n units of time. Coming back to the example, if we have to keep one book on a shelf. You will take one unit of time, for 10 books you will take 10 units of time. So, for n number of books, you will take n unit of time. The most important point that you need to remember is time depends on the number of books. The time can be represented as the order of n i.e. O(n). The time taken is in order of n.

In the next article, I am going to discuss User Input and Output in C# with Examples. Here, in this article, I try to explain Recursion in C# with Examples. I hope you enjoy this Recursion in C# with Examples article. I would like to have your feedback. Please post your feedback, question, or comments about this Recursion in C# with Examples article.

Leave a Reply

Your email address will not be published.