Recursion in C

In this tutorial, we will know what is the recursive function and what is recursion in C programming language? Difference between iteration and recursion. Advantages and disadvantages of recursion function.

A function that contains a call to itself is called the recursive function. A technique of defining the recursive function is called recursion. The recursive function allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

In general, programmers use two approaches to writing repetitive algorithms. One approach uses loops i.e. iteration and other approach uses recursion. Recursion is a repetitive process in which a function calls itself. Some older language does not support recursion. One major language that does not support is COBOL.

A recursive function must have at least one exit condition that can satisfy. Otherwise, the recursive function will call itself repeatedly until the runtime stack overflows. To prevent infinite recursion generally if-else (or similar approach) can be used where one branch makes the recursive call and other doesn’t.

Steps need for implementing recursion
1) Decomposition into smaller problems of the same type.
2) Recursive calls must diminish problem size
3) The necessity of the base case
4) The base case must reach
5) It acts as a terminating condition. Without an explicitly defined base case, a recursive function would call itself indefinitely.
6) It is the building block to the complete solution. In a sense, a recursive function determines its solution from the base case it reaches.

Iteration and recursion in C

let’s write a function to solve the factorial problem iteratively. This solution usually involves using a loop. The factorial of a number is the product of the integer values from 1 to the number.

Finding Factorial using non-recursive or using iteration technique

Factorial(n) = 1, if n=0
Factorial(n) = n * (n-1) * (n-2) * (n-3) ….3*2*1 if n>0

This definition is iterative. A repetitive function is defined iteratively whenever the definition involves only the parameter(s) and no the function itself.

Factorial(5) = 5*4*3*2*1

Program Description:- Program to find factorial of a given number using non-recursive or using iteration technique.

#include<stdio.h>
int factorial(int n);
int main()
{
   int number;
   printf("Enter an integer number: ");
   scanf("%d",&number);
   int result = factorial(number);
   printf("Factorial of %d = %d", number, result);
   return 0;
}
int factorial(int n)
{
   int i, fact=1;
   for(i=1; i<=n; i++)
   {
     fact *= i;
   }
   return fact;
}

Output:-

Enter an integer number: 5
Factorial of 5 = 120

Finding Factorial using recursion in C

The below program shows the recursive solution of finding factorial. This program does not need a loop; the concept itself involves repetition.

A repetitive function is defined recursively whenever the function appears within the definition itself.
Factorial(n) = 1, if n=0
Factorial(n) = n * factorial(n-1) if n>0

Program Description:- Program to find factorial of a given number using recursive function.

#include<stdio.h>
int factorial(int n);
int main()
{
   int number;
   printf("Enter an integer number: ");
   scanf("%d",&number);
   int result = factorial(number);
   printf("Factorial of %d = %d", number, result);
   return 0;
}
int factorial(int n)
{
   if(n==0) return 1;
   else return (n*factorial(n-1));
}

Output:-

Enter an integer number: 6
Factorial of 6 = 720

In the recursive solution, the function factorial call itself, each time with a different set of parameters.

Difference between Iteration and recursion

Both iteration and recursion are based on a control structure and repetition. Iteration explicitly uses a repetition structure but recursive uses a selection structure to achieve repetition through repeated function calls.

Iteration and recursion each involve a termination test. When the loop-continuation condition fails then the Iteration terminates. But, the recursion terminates when a base case recognized. Iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation fail, recursion keeps producing simpler versions of the original problem until the base case reach.

Both iteration and recursion can occur infinitely. An infinite loop occurs with iteration if the loop-continuation test never becomes false. Infinite recursion occurs if the recursion step does not reduce the problem each time in a manner that converges on the base case.

Designing recursive functions

In recursion, the statement that solves the problem is known as the base case. Every recursive function must have a base case. The rest of the function is known as the general case. The general case divides the big problem into small problems. In our factorial example, factorial(0) is the base case. At this point, recursion calls ended and starts calculating with the returning values. In the above factorial program n*factorial(n-1); is the general case. The general case contains the logic needed to reduce the size of the problem.

Note:- Every recursive call must either solve some part of the problem or reduce the size of the problem.
The following are rules for designing a recursive function.
1) First, determine the base case.
2) Then, determine the general case.
3) Finally, combine the base case and general case into a function.

In combining the base and general case into a function, we must pay careful attention to the logic. Each call must reduce the size of the problem and move it towards the base case. The base case, when reached, must terminate without a call to the recursive function; that is it must execute a return.

Limitations of recursion in C

Recursion allows the user to get results, without using loops due to this complexity of the program is reduced. Recursion reduces the calling of function by the user. By using recursion, we can control the function calling information or statements. By using recursion, we can evaluate stack expressions.

Recursion has many limitations. It repeatedly involves the mechanism, and consequently the overhead, of function calls. This can be expensive in both processor time and memory space. Since recursive call causes another copy of function (actually only the function’s variables) to be created, this can consume considerable memory. Iteration normally occurs within the function. So, the overhead of repeated function calls and extra memory assignment is omitted.

Recursive functions are slower than normal function due to stack overlapping. They can create StackOverflow because of occupying more stack. Recursive functions will create infinite loops also.

#include<stdio.h>
int main()
{
   printf("Welcome to KnowProgram.\n");
   main();
   return 0;
}

The above program causes infinite loops. To control the program we need to add some conditional statements.

#include<stdio.h>
int a = 1; // global variable
int main()
{
   printf("Welcome to KnowProgram.\n");
   a++;
   if(a<=5) main();
   return 0;
}

Any problem that can be solved recursively can also be solved iteratively. A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. Another reason to choose a recursive solution is that an iterative solution may not be apparent. Avoid using recursion in performance situations. Recursive calls take time and consume additional memory.

C Programming examples on Recursion:- Recursion program examples, Fibonacci Series using Recursion, Factorial using Recursion, GCD or HCF using Recursion

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search