Recursion in C

Back to: C Tutorials For Beginners and Professionals

Recursion in C Language with Examples

In this article, I will discuss the Recursion in C Language with Examples. Please read our previous articles discussing the Functions in C Language with Examples. At the end of this article, you will understand the following pointers with Examples.

1. What is Recursion in C Language?
2. Example to Understand Recursion in C Language
3. What Does It Mean by Recursive Function?
4. How Does Recursion Work in C?
5. Can we call the Main Function itself in C?
6. How are Recursive Functions Classified?
7. Advantages and Disadvantages of Recursion in C Language
8. When to Use Recursion in C Language?

What is Recursion in C Language?

Recursion in C language is a programming technique where a function calls itself directly or indirectly. This method solves problems that can be broken down into simpler, similar sub-problems. A recursive function typically has two main parts:

• Base Case: This is a condition under which the recursion ends. A recursive function would call itself indefinitely without a base case, leading to a stack overflow error.
• Recursive Case: This is where the function calls itself with a modified parameter, usually moving closer to the base case with each call.

Example to Understand Recursion in C Language:

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

First, we need to understand how this function call is made and how it works. Once I start executing the program, it will start executing it from the main function. First, it will execute the first statement, then the second statement, and then 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, second, and third statements. 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., the 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.

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 value returning from the fun function has to be added by two. So, this addition needs to be done once the fun function completes its execution and returns 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 once the fun function completes its execution. 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.

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

What Does It Mean by Recursive Function?

Function calling itself is called recursion. The function in which control is present, if it calls itself again, then it is called the 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 different 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.

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

In this example, the function will call itself 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, I have a main function with some value in the variable x and call function fun1 passing that variable x value. The function fun1 takes parameter n, which will accept the x value, and if the condition is true, it prints the value n and then calls itself by passing the reduced value on n by 1. 

void fun1(int n)
{
    if(n>0)
    {
        printf("%d ",n);
        fun1(n-1);
    }
}
void main()
{
    int x=3;
    fun1(x);
}

Output: 3 2 1

In the above example, we are passing 3 to the fun1 function from the main function. Let us see what the result will be 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, two statements must 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. That means the condition to stop the recursive call is when the n value becomes 0.

Let’s start tracing. We call function fun1 passing, x, i.e., value 3 from the main function. 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, 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 was calling itself again.

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

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

Now, fun1(0), 0 is greater than 0. No, it’s not greater than 0. So, it will not enter inside, perform those two steps, and do nothing. So, no printing and no calling will not enter inside, and it will come outside of the function. 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 a tracing tree of a recursive function. Now, we will take one more example.

Example:

Please look at the example below, which is also an example of the recursive function.

void fun2(int n)
{
   if(n>0)
   {
       fun2(n-1);
       printf("%d",n);
   }
}
void main()
{
   int x=3;
   fun2(x);
}

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

If you look at the main function of both the examples, they have 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 examples is that in example 1 inside the fun2 function, if the condition is true (i.e., n > 0), first it prints the n value and then calls itself, but in example 2, first, it calls 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 the 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 must be finished to execute the second statement i.e., printing. For a better understanding, please have a look at the below image.

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 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 look like it is below.

Let us trace fun2(1). Again, 1 is greater than 0; hence, the condition is satisfied, and again two steps. In the first step, it will call itself passing 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.

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.

Once this call has been terminated, the control should return 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; hence, it will print 1. For a better understanding, please have a look at the below image.

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 two is printed then it will come out of this function and finish. For a better understanding, please have a look at the following image.

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 three is printed. The output from this function is 1 2 3, as shown in the image below.

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

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

Example: Calculate the Factorial of a Number Using Recursive Functions in C Language

int factorial (int n)
{
      if(n==1)
          return (1);
      return(n*factorial(n-1));
}

Here, the factorial function will call itself but with a smaller value of n. The complete program is given below.

#include <stdio.h>
int factorial(int number);
int main() 
{    
    int x = 6;
    printf("The factorial of %d is %d\n", x, factorial(x)); 
    return 0;
}
int factorial(int number) 
{
 	if (number == 1)    
        return (1); /* exiting condition */
  	else
    	return (number * factorial(number - 1));
}

Output: 

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 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.

Can we call the main function itself in C?

The main() function can be called itself, but if we use the auto variable, it becomes a stack overflow error. Let us see the program for a better understanding.

#include <stdio.h>
int main()
{
    int a = 5;
    ++a;
    printf("%d", a);
    if(a <= 6)
        main();
        printf("%d", a);
    return 0;
}

Output:

Example to calculate the power of a number using the Recursive Function in C.

#include <stdio.h>
int power(int b, int e)
{
    if(e < 0)
        return 0;
    else if(e == 0)
        return 1;
    else
        return( b * power(b, e-1));
}
int main()
{
   int a, b, p;
   printf("Enter the value of a : ");
   scanf("%d" , &a);
   printf("Enter the value of b : ");
   scanf("%d" , &b);
   p = power(a, b);
   printf("%d^%d value is %d", a, b, p);
   return 0;
}

Output:

How are Recursive Functions classified?

Recursions are classified into two types.

1. Internal recursive process
2. External recursive process

If one recursive function calls itself, it is called the internal recursive process. If one recursive function calls another, it is called an external recursive process.

Advantages and Disadvantages of Recursion in C Language

Recursion in the C programming language, as in other programming languages, offers advantages and disadvantages. Here’s a breakdown of both:

Advantages of Recursion in C Language

• Simplicity in Problem Solving: Recursion provides a clear and simple way to solve complex problems by breaking them down into smaller, more manageable sub-problems. This is particularly useful for problems naturally suited to recursive solutions, like tree traversals, graph explorations, and algorithms like QuickSort or MergeSort.
• Reduction of Code Complexity: Recursive functions can lead to cleaner and more understandable code, as they allow a complex task to be defined in a simple recursive manner, reducing the need for extensive looping constructs and multiple variables.
• Ease of Maintenance: Recursive code is often easier to read and understand, making maintenance and debugging more straightforward.
• Facilitates the use of Data Structures: Recursion is a natural fit for working with recursive data structures like trees and graphs, providing an intuitive approach to algorithms like DFS (Depth-First Search), BFS (Breadth-First Search), etc.

Disadvantages of Recursion in C Language

• Performance Overhead: Recursive calls involve extra overhead due to repeated function calls and return statements. Each recursive call uses stack space; too many calls can lead to stack overflow. This is less efficient than iterative solutions, especially for problems that involve simple repetitions.
• Memory Usage: Each recursive call requires its own space in the call stack. This can lead to significant memory use for deep recursion, increasing the risk of stack overflow, particularly in environments with limited stack size.
• Debugging Difficulty: Debugging recursive functions can be more challenging than iterative ones. Understanding the flow of recursive calls and maintaining the state at each level can be complex.
• Risk of Infinite Recursion: If the base case is not defined properly, or the recursive step does not approach the base case, it can result in infinite recursion, leading to program crashes or stack overflow errors.
• Tail Recursion Optimization Dependency: The compiler can optimize Some recursive functions through tail recursion optimization. However, not all compilers implement this optimization; without it, even tail-recursive functions can be inefficient regarding stack space usage.

When to Use Recursion in C Language?

Here are scenarios when recursion is typically used in C:

• Problem Naturally Fits Recursive Logic: Some problems are inherently recursive, such as tree traversals, solving the Tower of Hanoi, or generating Fibonacci numbers. In such cases, recursion provides a clear and concise solution.
• Simplification of Code: Recursion can simplify the code for certain problems, making it more readable and maintainable. This is often the case in divide-and-conquer algorithms, like quicksort and mergesort.
• Backtracking Situations: Recursion is useful in scenarios where you need to explore multiple possibilities and then backtrack, such as in graph algorithms (like depth-first search) or solving puzzles (like Sudoku).
• Dynamic Programming Problems: Recursion with memoization (storing results of expensive function calls) is often used in dynamic programming to optimize the solution of overlapping subproblems, like in calculating the nth Fibonacci number.
• Mathematical Computations: Certain mathematical computations are expressed more naturally and elegantly with recursion, such as calculating factorials or performing certain numerical integrations.

In the next article, I will discuss How Recursion uses Stack in C Language with Examples. In this article, I try to explain recursive functions in C language with examples. I hope you enjoy this article on recursive functions in C language with examples. I would like to have your feedback. Please post your feedback, questions, or comments about this recursive function in the C article.