Types of Recursion in C 

Types of Recursion in C 

6 mins read718 Views Comment
clickHere
Updated on Mar 17, 2023 14:43 IST

Recursion is a process in which a particular procedure is repeated in a similar manner until a specific condition is met. Recursion can be a powerful tool for solving certain types of problems, particularly those that involve repeated subtasks that can be broken down into smaller, similar subtasks.

2023_03_MicrosoftTeams-image-342.jpg

For example, you can use recursive functions to traverse tree structures or to perform mathematical operations such as factorials or Fibonacci sequences. In this article, we will discuss the types of recursion in C programming language.

We will be covering the following sections: 

Introduction to Recursion in C 

Recursion in C is a technique where a function calls itself during its execution. This means that the function will keep calling itself until a certain condition is met, after which it will return control to the calling function. The function which calls itself is called a recursive function, and the function call is known as a recursive call

Recursion is comparable to iteration, but it is more complicated to comprehend. If a problem can be solved by recursion, it can also be solved by iteration. You can use recursive functions to solve problems such as sorting, traversal, and searching. It is crucial to include a base (exit) condition while using recursion; otherwise, the program will go into an infinite loop.  

A recursive method or function has two cases in its program body:  

  • Base case – a specific condition in the function that terminates the recursion, and 
  • Recursive case – the part of the code inside the recursive function that is executed repeatedly while the function is calling itself. 

You can also explore: What are C rand() and srand() Functions?

Syntax of Recursion 

The syntax of recursion in C involves a function that calls itself during its execution. Here is a general syntax for recursive function in C: 

 
return_type function_name(parameters) {
if (base_condition) {
// base case: stop recursion
return base_value;
}
else {
// recursive case: call the function recursively
return function_name(modified_parameters);
}
}
Copy code

You can also explore: Understanding Multidimensional Array in C

How Recursion Works? 

The steps involved in a recursive function are as follows: 

  • The function checks whether a base condition has been met. If it has, the function returns a base value that terminates the recursion. 
  • If the base condition has not been met, the function calls itself with modified parameters. 
  • The function continues to call itself recursively until the base condition is met. 
  • Once the base condition is met, the function returns the final result of the recursion. 

Note that the base case is essential to prevent infinite recursion, which could result in a stack overflow errors. It is also important to make sure that the modified parameters passed to the recursive call bring the function closer to the base case with each iteration. 

You can also explore: Structure in C Programming: How to Create and Use Programs

Types of Recursion in C 

There are two types of recursion in C language: 

  • Direct Recursion 
  • Indirect Recursion 

Let’s look at both of these types in detail below: 

You can also explore: Tokens in C Programming: Keywords, Identifiers, Constants, and Operators

Direct Recursion in C 

Direct recursion is a type of recursion in which a function calls itself directly. Here is the syntax of direct recursion in C: 

 
return_type function_name(parameters) {
// base case
if (condition) {
// return some value
}
// recursive case
else {
// modify parameters
// call the same function with modified parameters
function_name(modified_parameters);
}
}
Copy code

Here is an example of a direct recursive function in C that calculates the factorial of number 5: 

 
#include <stdio.h>
int factorial(int n) {
// base case
if (n == 0 || n == 1) {
return 1;
}
// recursive case
else {
return n * factorial(n - 1);
}
}
int main() {
int n = 5;
int result = factorial(n);
printf("Factorial of %d is %d\n", n, result);
return 0;
}
Copy code

Output: 

Factorial of 5 is 120 

In this example, the factorial() function is a direct recursive function that calculates the factorial of a number. If the input number is 0 or 1, the base case is met, and the function returns 1. If the input number is greater than 1, the function calls itself with a modified parameter (n – 1), which eventually reaches the base case. Finally, the function returns the result of the recursion, which is the factorial of the input number. 

When the main() function is executed, it calls the factorial() function with an input of 5, which is calculated recursively until the base case is met. The final result of the recursion is returned and printed to the console. 

You can also explore: Learning About Pointers in C

Indirect Recursion in C 

Indirect recursion is a type of recursion in which two or more functions call each other in a circular manner to achieve a common goal. Here is the syntax of indirect recursion in C: 

 
return_type function_name_1(parameters) {
// base case
if (condition) {
// return some value
}
// recursive case
else {
// call the second function with modified parameters
function_name_2(modified_parameters);
}
}
return_type function_name_2(parameters) {
// base case
if (condition) {
// return some value
}
// recursive case
else {
// call the first function with modified parameters
function_name_1(modified_parameters);
}
}
Copy code

Here is an example of indirect recursion in C that prints the even and odd numbers from 1 to a given limit: 

 
#include <stdio.h>
void print_odd(int n);
void print_even(int n) {
// base case
if (n == 0) {
return;
}
// recursive case
else {
printf("%d ", n);
print_odd(n - 1);
}
}
void print_odd(int n) {
// base case
if (n == 0) {
return;
}
// recursive case
else {
printf("%d ", n);
print_even(n - 1);
}
}
int main() {
int limit = 10;
printf("Even numbers from 1 to %d: ", limit);
print_even(limit);
printf("\nOdd numbers from 1 to %d: ", limit);
print_odd(limit);
return 0;
}
Copy code

Output: 

2023_03_image-48.jpg

In this example, two functions print_even() and print_odd() are defined. They call each other to print the even and odd numbers from 1 to a given limit. The print_even() function prints the even numbers by calling the print_odd() function with a modified parameter (n – 1). The print_odd() function prints the odd numbers by calling the print_even() function with a modified parameter (n – 1). This process continues until the base case is reached, which is when the input parameter becomes 0. 

When the main() function is executed, it calls both print_even() and print_odd() functions with a limit of 10, which are called indirectly to print the even and odd numbers. The final output is printed to the console. 

You can also explore: Implementing arrays in C programming

Difference between Recursion and Iteration 

Both recursion and iteration are useful techniques for solving programming problems, and the choice of which one to use will depend on the specific requirements and constraints of the problem at hand.  

Here is a table outlining the key differences between recursion and iteration:

Recursion  Iteration 
Involves calling a function from within the same function  Involves repeating a set of instructions using loops 
Can be more elegant and concise in some cases  Can be more straightforward and efficient in some cases 
Uses more memory as each recursive call creates a new stack frame  Uses less memory as it doesn’t create new stack frames 
Can be more difficult to debug and understand  Can be easier to debug and understand 
Can lead to stack overflow if the base case is not reached  Can lead to an infinite loop if the loop condition is not written correctly 
Used for solving problems that can be broken down into smaller sub-problems  Used for performing a set of instructions repeatedly 

You can also explore: Introduction to Linked List Data Structure

Must explore: C Programming Online Courses & Certifications

Endnotes 

Hope this article was helpful for you to understand the types of recursion in C and how recursion varies from iteration. If you want to learn more about C programming and solidify your basics, you can explore our articles on C. 

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio