Recursion in C

Recursion in C: In the C programming language, the concept known as recursion exists that is a technique in which a function calls itself either directly or indirectly. It allows the developer to express the operations within the terms of themselves. The concept of recursion is a process that comes into the picture when any of the underlying functions call a copy of itself in order to work on a similar type of query.

Any function in a program that calls itself is termed a recursive function, and the function calls are referred to as recursive calls. The recursion indulges numerous recursive calls in its lifetime. However, it is tedious to terminate such recursion conditions.

Recursive codes are shorter when compared with iterative code, but it isn't easy to understand in general.Recursion is a type of algorithm that cannot be applied to every problem.

Although it is more beneficial for problems defined in terms of subproblems such as, it can be applied to many problems that include traversal, sorting techniques, searching, etc. It can be concluded that iterative solutions are more efficient than recursion as the function call is always overhead.

A simple way of learning recursion is to imagine them being in a process where one of the instructions is set to repeat themselves. This concept sounds very much similar to looping as it repeats the same code.

On the contrary, a recursion makes it easier to express the ideas in which the result of the recursive call is necessary to complete a particular work. However, the program or the process can complete without the intervention of a recursive call.

Usage of a recursive algorithm to solve the problem is relatively easy. All the problems which can be solved recursively can be solved iteratively, but all the problems solved iteratively cannot be solved recursively.

Recursion is best acquainted for solutions, problem statements that include the tower of Hanoi, Fibonacci series, factorial, inorder or postorder or preorder tree traversals, graphs, and so on.

Syntax

 void recursion(void)
 {
 recursion(); /* function calls itself */
 }
 int main(void)
 {
 recursion();
 return 0;
 } 

When recursion is being implemented, one must be careful in deliberating an exit condition, or a terminating condition form the recursive function; else, it will continue as an infinite loop.

Recursive Function

Recursive functions perform tasks by dividing them into subtasks. There will be termination conditions defined in the function, which will be satisfied by some of the subtasks. In some cases, the function may not recur referred to as a base class, while some cases where the function keeps calling the same function to perform a sub task is referred to as a recursive case.

 if (base1 test)
 {
 return first_value;
 }
 else if (base2 test)
 {
 return second_value;
 }
 else
 {
 /* solution for problem statement */
 recursive calls;
 } 

Recursion keeps on running until an exit condition is met. In order to prevent the infinite recursion, the “if..else” statement is used where one uses a recursive call while the other does not.

Example of a recursive function for getting sum of numbers

 #include <stdio.h>
 #inlcude<conio.h>
 int sum(int n);
 int main()
 {
 int number, result;
 printf("Enter a positive integer: ");
 scanf("%d", &number);
 result = sum(number);
 printf("sum = %d", result);
 return 0;
 }
 int sum(int n) {
 if (n != 0)
 /* sum() function calls itself */
 return n + sum(n-1);
 else
 return n;
 } 

Output

In the above given instance, the function ‘sum()’ is being called from the main() function along with the ‘number’ passed as an argument. If the value of the variable ‘n’ within the function ‘sum()’ is 3 in the beginning, in the next call, 2 will be passed to the ‘sum()’ function.

This will continue until the variable ‘n’ becomes 0. Once the value of the variable ‘n’ is equal to 0, then the ‘if’ loop fails, and then the ‘else’ loop will be executed by terminating the program and returning the sum of the integers to the ‘main()’ function.

Factorial of a number

 #include <stdio.h>
 #inlcude<conio.h>
 int f(int n)
 {
             if (n == 0 || n == 1) /*terminating or exit condition
                         return 1;
             else
                         return n * f(n - 1); /* Recursive condition */
 }
 int main()
 {
             int n = 5;
             printf("The factorial of the number %d is: %d", n, f(n));
             return 0;
 } 

Output

A Fibonacci sum of a series

 #include<stdio.h>
 #include<conio.h>
 int fibonacci(int); 
 void main () 
 { 
 int n,f; 
 printf("Enter the value of the number '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); 
 } 
 }  

Output

Advantages of using recursion

• Recursion makes the program look more elegant.
• The performance of the recursion is vital as it uses loops.
• It reduces the time complexity.
• It is the best concept to use in the tree traversal.
• It gives clarity and reduces the debugging time.

Disadvantages of using recursion

• It uses more memory than required.
• It keeps on looping until the termination condition is met.