Types of Recursion in C
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.
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
- How Recursion Works?
- Types of Recursion in C
- Difference between Recursion and Iteration
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); } }
You can also explore: Understanding Multidimensional Array in C
Best-suited Programming courses for you
Learn Programming with these high-rated online courses
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); } }
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; }
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); } }
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; }
Output:
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.
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
Top Picks & New Arrivals
