Recursion in C

Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls. However, it is important to impose a termination condition of recursion. Recursion code is shorter than iterative code however it is difficult to understand.
Recursion cannot be applied to all the problem, but it is more useful for the tasks that can be defined in terms of similar subtasks. For Example, recursion may be applied to sorting, searching, and traversal problems.
Generally, iterative solutions are more efficient than recursion since function call is always overhead. Any problem that can be solved recursively, can also be solved iteratively. However, some problems are best suited to be solved by the recursion, for example, tower of Hanoi, Fibonacci series, factorial finding, etc.

                          
#include <stdio.h>  
int fact (int);  
int main()  
{  
    int n,f;  
    printf("Enter the number whose factorial you want to calculate?");  
    scanf("%d",&n);  
    f = fact(n);  
    printf("factorial = %d",f);  
}  
int fact(int n)  
{  
    if (n==0)  
    {  
        return 0;  
    }  
    else if ( n == 1)  
    {  
        return 1;  
    }  
    else   
    {  
        return n*fact(n-1);  
    }  
}

                     
                    

We can understand the above program of the recursive method call by the figure given below:

Recursive Function

A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.
The case at which the function doesn't recur is called the base case whereas the instances where the function keeps calling itself to perform a subtask, is called the recursive case. All the recursive functions can be written using this format.

Example of recursion in C

Let's see an example to find the nth term of the Fibonacci series.

            
#include <stdio.h>

#include <stdio.h>  
int fibonacci(int);  
void main ()  
{  
    int n,f;  
    printf("Enter the value of n?");  
    scanf("%d",&n);  
    f = fibonacci(n);  
    printf("%d",f);  
}  
int fibonacci (int n)  
{  
    if (n==0)  
    {  
        return 0;  
    }  
    else if (n == 1)  
    {  
        return 1;   
    }  
    else  
    {  
        return fibonacci(n-1)+fibonacci(n-2);  
    }  
}
            
        

Memory allocation of Recursive method

Each recursive call creates a new copy of that method in the memory. Once some data is returned by the method, the copy is removed from the memory. Since all the variables and other stuff declared inside function get stored in the stack, therefore a separate stack is maintained at each recursive call. Once the value is returned from the corresponding function, the stack gets destroyed. Recursion involves so much complexity in resolving and tracking the values at each recursive call. Therefore we need to maintain the stack and track the values of the variables defined in the stack.
Let us consider the following example to understand the memory allocation of the recursive functions.

Fibonacci Sequence

The Fibonacci sequence is another classic example of recursion. The sequence starts with 0 and 1, and each subsequent number is the sum of the previous two:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

The base cases are Fibonacci(0) = 0 and Fibonacci(1) = 1.

                        
#include <stdio.h>
int fibonacci(int n) 
{
    if (n == 0)
        return 0; // Base case
    else if (n == 1)
        return 1; // Base case
    else
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
    
int main() 
{
    int num = 6;
    printf("Fibonacci of %d is %d\n", num, fibonacci(num));
    return 0;
}
                        
                    

Sum of Natural Numbers

Another common recursive example is the calculation of the sum of the first n natural numbers.

sum(n) = n + sum(n-1)

The base case is when n = 0, where the sum is 0.

                        
#include <stdio.h>
int sum(int n) 
{
    if (n == 0)
        return 0; // Base case
    else
        return n + sum(n - 1); // Recursive case
}
    
int main() 
{
    int num = 5;
    printf("Sum of first %d natural numbers is %d\n", num, sum(num));
    return 0;
}
                        
                    

Power of a Number

We can use recursion to compute the power of a number. The power function can be defined as:

power(base, exp) = base * power(base, exp - 1)

The base case is when exp = 0, where the result is 1.

                        
#include <stdio.h>
int power(int base, int exp) 
{
    if (exp == 0)
        return 1; // Base case
    else
        return base * power(base, exp - 1); // Recursive case
}
    
int main() 
{
    int base = 2, exp = 3;
    printf("Power of %d raised to %d is %d\n", base, exp, power(base, exp));
    return 0;
}