Recursion in C

The C programming language offers various features which help the programmers in making their code efficient and simple. In C, Recursion is one of the most complex and useful concepts.

With the help of recursion, you can solve complex mathematical problems such as factorial of a number and generating fibonacci series etc.

Let us see what is Recursion in C?

Recursion in C

In C, When a function calls a copy of itself then the process is known as Recursion. To put it short, when a function calls itself then this technique is known as Recursion. And the function is known as a recursive function.

You have to be more careful when you are using recursion in your program. You just cannot use recursion in all your problems because it will make your program more complex and difficult.

Recursion can be used in case of similar subtasks like sorting, searching, and traversal problems. While using recursion, you will have to define an exit condition on that function, if not then it will go into an infinite loop.

NOTE:- Problems that can be solved recursively, can also be solved iteratively.

Syntax of recursive function in C:-

void do_recursion()
{
    ... .. ...
    do_recursion();
    ... .. ...
}
int main()
{
    ... .. ...
   do_recursion();
    ... .. ...
}

Working of recursion in C:-

Below is a flowchart of how recursion works:-

The recursion will go in an infinite loop until some condition is met. So, to prevent it from going into an infinite loop, you can make use of the if…else statement or define an exit condition in the recursive function.

Example:- Infinite loop through recursive function

#include<stdio.h>

int main()
{
  printf("TechVidvan Tutorial: Infinite loop through Recursive Function!\n");
  main();
  return 0;
}

The above example will result in an infinite loop. In the above program, we are doing recursion by calling main() from main(). And also we have not provided any condition for the program to exit. That’s why it will print the output infinitely.

Types of recursion in C

There are two types of recursion present in the C programming language.

• Direct Recursion
• Indirect Recursion

1. Direct Recursion in C

If a function calls itself directly then the function is known as direct recursive function.

Example:- Direct Recursive function in C

int fib(int num)
{
    if (num==1 || num==2)
        return 1;
    else
        return (fib(num-1)+fib(num-2));
}

In the above example, fib() function is direct recursive. Because the statements inside the fib() function calls the fib() function directly.

2. Indirect Recursion in C

A function that does not call itself directly then function is known as an indirect recursive function.

Example:- Indirect Recursive function in C

int first_function(int num)
{
    if (num<=2)
        return 2;
    else
        return new_function(num);
}
int new_function(int num)
{
    return first_function(num);
}

In the above example, first_function() calls the new_function(), which is indeed a new function. Then this new_function() calls the first_function(). So, it is an indirect recursive function.

Example:- Finding factorial of a given number

#include <stdio.h>  
int factorial(int);  
int main()  
{  
  int num=5,fact;  
  printf("TechVidvan Tutorial: Factorial of a number using recursion!\n\n");  
  fact = factorial(num);  
  printf("Factorial of %d is: %d\n",num,fact);  
}  
int factorial(int num)  
{  
if (num==0)  
{  
return 0;  
}  
else if (num==1)  
{  
return 1;  
}  
else   
{  
return num*factorial(num-1);  
}  
}

Output:-

Recursive Function in C

A recursive function always performs tasks by dividing it into subtasks. In a recursive function, there has to be an exit() condition and when it is satisfied then the recursion stops and the final result is returned from the function.

For Example:-

if (condition1)  
{  
  return value1;  
}  
else if (condition2)  
{  
  return value2;  
}  
else  
{  
  // Statements;  
  recursive call;  
}

Example:- Recursive Function

#include<stdio.h>  
int fib(int);  
void main ()  
{  
  int num=15,fibo;  
  printf("TechVidvan Tutorial: Fibonacci series using recursive function!\n\n");
  fibo = fib(num);  
  printf("Result is: %d",fibo);  
}  
int fib(int num)  
{  
  if (num==0)  
  {  
  return 0;  
  }  
  else if (num == 1)  
  {  
    	return 1;   
  }  
  else  
  {  
    	return fib(num-1)+fib(num-2);  
  }  
}

Output:-

Memory allocation of recursive method:-

In C, each recursive function call creates a copy of it in memory. When some data is returned from the recursive call then the memory releases the copy.

As we all know that all variables, arguments and other things of function get stored in the stack. And for each recursive call, a separate stack is maintained.

Let’s take an example to understand the memory allocation of recursive method.

int print(int num)  
{  
  if(num == 0)  
    	return 0;  
  else   
  {  
    	printf("Value is: %d",num);  
    	return print(num-1); // recursive call  
  }  
}

Let’s analyze the above example for num=4. At first, all stacks are maintained. We have used the if condition in the above example. If the value of num reaches 0 then the stacks will be deleted one by one by returning 0 to its calling stack.

Advantages of Recursion in C

• Makes the program elegant.
• It adds clarity to the program code and also reduces the time to write the code.
• Reduces time complexity.
• It is best for solving problems based on tree structures.

Disadvantages of Recursion in C

• It is slower than non recursive programs due to the overhead of maintaining the stack.
• It requires more memory for the stack.
• For better performance, use loops instead of recursion. Because recursion is slower.

Significance of Recursion in C

In C, programmers use recursion many times on their programs due to its ability to keep the code short and simple. It also enhances the code readability.

Recursion also helps in reducing the run-time of the program code. But you can also use iteration, it provides much faster functionality than recursion.

You can solve several problems using the recursion in C. Problems like factorial of a number, fibonacci series in a given range, tree algorithm problems etc. can be solved easily with recursion.

Why stack overflow occurs in recursion:-

In recursion, if you don’t specify or define the base case then you can face stack overflow problems.

Example:-

int factorial(int num)
{
    // wrong base case
if (num == 10) 
        return 1;
    else
        return num*factorial(num-1);
}

In the above example, if you provide factorial(5) then first it will call factorial(4), factorial(3) and so on but the number will never reach 10. So, here the base case is not reached then the memory will get exhausted by the factorial() functions on the stack and it will cause a stack overflow error.

Difference between tailed and non-tailed recursion in C

In a recursive function, if the recursive call is the last thing executed by the recursive function then the recursive function is known as tail-recursive. And if it is not then it is called a non-tailed recursive.

Summary

In this tutorial, we learnt about recursion and recursive functions. We also discussed advantages and disadvantages of using recursion. We also discussed the types of recursion in C.