What is Recursion in C? Types, It's Working, and Examples

In a program, every function written in the C programming language can call itself multiple times. Recursive functions are defined as any function that calls itself repeatedly (directly or indirectly) until the program satisfies a specified condition or subtask. In this article, learn the recursion in C and its applications. 

Let us see what is Recursion in C?

What is C Recursion?

Recursion in C is a process where a function calls itself to solve a problem. It allows a complex problem to be broken down into simpler sub-problems, each of which is solved by invoking the same function. C Recursion requires a base case that stops the recursive calls, preventing infinite loops. 

Recursion in C results when a function calls a duplicate of itself to work on a smaller problem. This recursive function is any function in the C programming language that calls itself. 

Meanwhile, these calls–made by the recursive functions–are called recursive calls. There are numerous recursive calls involved in C recursion. Nevertheless, it's crucial to impose a recursion termination condition. Although recursive code is shorter than iterative code, it is more cryptic. 

Learn More: Advantages and Disadvantages of Arrays in C, C++, and Java

How Does C Recursion Work?

In the C programming language, recursive functions are easy to comprehend. It entails specific duties that are broken down into different subtasks. There are termination conditions or conditions in some of the subtasks. 

To end the program, these subtasks must meet these requirements. Otherwise, as was already mentioned, a never-ending cycle will be produced. 

Also, at the end of the C recursion, you can determine the final outcome by leveraging the recursive function. The idea of the basic case is also present here. The recursive function may attempt to complete a subtask on numerous occasions by continually invoking itself. The recursive case is the name given to it. 

Let's examine the structure utilized to write the recursive function in the C language. 

recursive_function()
{
    //base case
    if base_case = true;
    return;
    
    else
    //recursive case
    return code_for_recursion; //includes recursive call
}

Syntax and Examples of C Recursion

Let us take a look at the format used for writing the recursive function in C with the help of syntax and examples.

Syntax:

Below is the syntax of recursion in c to make you understand better.

C
void recursive_function(int n) {
  // base case
  if (n == 0) {
    // do something
  } else {
    // recursive call
    recursive_function(n - 1);
    // do something else
  }
}

Example:

Below is the example of recursion in c:

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

Once the base case is reached, this function continues to call itself in a recursive fashion. The method returns 1 in the basic case, which occurs when the number is 0. If not, the function increases the value by the number's factorial minus 1. 

What is C Recursion Used for?

In C, recursion is frequently used for operations like factorial calculation, list sorting, and tree searching. Here are some specific applications of C recursion.

Recursion can be used to order data lists, such as strings or numeric lists. Tree searches: Trees are data structures for storing and retrieving data, and they can be searched via recursion. 

Properties of C Recursion

• Users can execute the same processes with different inputs numerous times. 
• Users can attempt smaller inputs at each step to reduce the problem. 
• A base condition must terminate the C recursion; otherwise, it will continue indefinitely. 

Memory Allocation of Recursive Method in C

That method is duplicated in memory with each recursive call. The copy is erased from memory after the procedure returns some data. At each recursive call, a distinct stack is maintained since all variables and other items declared inside the function are saved on the stack. 

Upon receiving the value from the relevant function, the stack is deleted. Resolving and keeping track of the values at each recursive call requires much complexity in recursion. As a result, we must keep the stack up to date and monitor the variables' values. 

Let's look at the example below to comprehend how recursive functions allocate memory. 

int display (int n)  
{  
    if(n == 0)  
        return 0; // terminating condition  
    else   
    {  
        printf("%d",n);  
        return display(n-1); // recursive call  
    }  
}

Explanation of Recursion in C

A function that calls itself repeatedly, either directly or indirectly, until it reaches its base case is known as a recursive function. A recursive call, which is contained inside the recursive function and calls it, is present. 

When a function reaches the base case, the recursive calls are terminated, and the copies in memory to return all of the values that were provided to them after each recursive call. The recursive function is ended after all of the values have been returned. 

The recursive_fun() function is shown in the previous figure. Recursive calls are contained within recursive_fun(). 

Advantages of C Recursion

• Simplicity: Code gets cleaner and uses fewer needless function calls. 
• Elegant solution: Helpful for resolving difficult algorithms and formula-based challenges. 
• Tractable approach: They are useful for traversing trees and graphs because they are naturally recursive. 
• Code reusability: Recursive functions in C can be used repeatedly within the program for different inputs, promoting code reusability.

Disadvantages of C Recursion

• Complexity: It gets challenging to read and decipher the code. 
• Stack consumption: The copies of recursive functions take up a significant amount of memory. 
• Performance: Recursive calls can be slower and less efficient than iterative solutions due to function call overhead and repeated calculations.
• Limited applicability: Not all problems are well-suited for C recursion, and converting iterative solutions into recursive ones may not always be practical or beneficial.

Types of Recursion in C

There are primarily two types of C recursion:

Direct Recursion: In this type of C recursion, a function calls itself directly. It is the most common form of recursion, where a function invokes itself during its execution.

Example:
void directRecursion(int n) {
    if (n > 0) {
        printf("%d ", n);
        directRecursion(n - 1);
    }
}

Indirect Recursion: In this type C recursion, multiple functions call each other in a circular manner. A function calls another function, which in turn may call the first one or another function, creating a chain of recursive calls.

Example:

void functionB(int n);

void functionA(int n) {
    if (n > 0) {
        printf("%d ", n);
        functionB(n - 1);
    }
}

void functionB(int n) {
    if (n > 1) {
        printf("%d ", n);
        functionA(n / 2);
    }
}

Both direct and indirect recursion have their use cases and are important concepts for solving certain types of problems. However, it is crucial to handle the termination condition properly to avoid infinite recursion.

What is the Difference Between Tailed And Non-Tailed Recursion?

Below is the quick difference between trailed and non-trailed recursion in C:

Real Applications of C Recursion 

In this section, explore the various real-life applications of C recursion. 

• Finding Data Structures Like Trees & Graphs: One can leverage the recursive methods to thoroughly explore and access a tree of graph’s nodes. 
• Divide-and-Conquer Algorithms: Algorithms like the binary search algorithm leverages this recursion technique to split the issues into smaller sub-issues. 
• Fractal Generation: Recursive algorithms can be used to create fractal shapes and patterns. For instance, the Mandelbrot set was created by continually applying complex numbers to a recursive algorithm. 
• Algorithms for Backtracking: Backtracking algorithms are implemented to handle issues that need a series of decisions, each of which is dependent on the prior one. 

Recursion in C can be used to create these algorithms to examine every avenue and go backward when a solution cannot be found. 

Conclusion

Recursion in C is a crucial idea in light of this. It is extensively utilized in algorithms and data structures. Recursion is frequently used, for instance, to solve issues like tree traversal. 

So, want to learn more about recursion in C and excel in this programming language? Get started with HeroVired’s Data science and analytics course today!