Recursion in C

Introduction

What do we mean by recursion in C? What are the different types of recursion in C? Are these some of the many questions bothering you? Let’s explore some of the most popular Recursion in C questions, including its types, advantages and disadvantages.

So, buckle up, and let’s get started.

What is Recursion in C?

Recursion can be described as a unique process of making a function call either directly or indirectly. It solves various problems, such as the DFS of Graph and the Tower of Hanoi. It breaks down complex problems into smaller subproblems and solves them gradually until a base case is reached.

Recursion in C offers flexibility, allowing for recursive calls as needed without limitations.

Using recursion in C programming offers numerous advantages. The benefits of applying recursion in C are evident in various scenarios.

Problem-Solving - Recursion occurs by breaking down a complex problem into small and simpler subproblems. This, in turn, enables programmers to approach in a more manageable way since they can now focus on the smaller, self-contained units.

Code Readability - Applying recursion also helps to generate concise and elegant code. They are more intuitive and easier to understand, enhancing their readability and maintainability.

Handling Recursive Data Structures - Recursion facilitates working with complex data structures such as graphs, trees, or linked lists. It can minutely manipulate such structures, as and when required, in a straightforward manner.

Basic Syntax of Recursion

Format of recursive functions

Writing a recursive function is very similar to reading one. It consists of the following components.

• Base Case - It is defined as a specific condition in the function, typically responsible for terminating the recursive function. When the base case is met, the recursive call stops and the function starts returning values. Therefore, it is always advisable to define base cases efficiently to avoid infinite recursions.
• Recursive Case - It is defined as the process of breaking down the original problem into smaller specific subproblems. Each recursive case operates on a small portion of the problem until the base case is reached.
• Return Statement - In a recursive function, it is possible to have multiple return statements that determine the value to be returned when the base case is reached.
• Function Arguments - In a recursive function, multiple arguments can be used, and they are modified in each recursive call to generate new outputs for subsequent calls.

Examples of simple recursive functions

Let’s explore a few examples of simple recursive functions in C.

Sum Of Natural Numbers

Look at how you can find the sum of natural numbers using the recursive function in C.

int sumOfNaturalNumbers(int n) {
// Base case: sum of 0 is 0
if (n == 0) {
return 0;
}
// Recursive case: sum(n) = n + sum(n-1)
return n + sumOfNaturalNumbers(n - 1);
}

Countdown

By utilising this function, we can observe a countdown starting from a positive integer down to 1. The algorithm for this process is outlined below.

void countdown(int n) {
// Base case: countdown reached 1
if (n == 1) {
printf("1\n");
return;
}
// Recursive case: print n and perform countdown(n-1)
printf("%d\n", n);
countdown(n - 1);
}

Explanation of base cases and recursive cases

You must balance base and recursive cases to create effective recursive functions in C. This brings us to the question, what exactly are these? Let’s find out.

Base Cases

Base cases in recursive functions have distinct characteristics. They have specific conditions that allow the function to compute and generate a result directly. They represent the simplest form of the original problem and do not require further recursion.

Recursive Cases

Recursive cases break down a complex problem into smaller-sized problems, aiming to reduce problem size or complexity. Multiple recursive calls to a function are possible, often with modified inputs or parameters.

Flowchart of Recursion

Understanding Recursion Through a Flowchart

Types of Recursion

Depending on the structure followed by the recursive function, we can divide it into two types.

• Linear Recursion
• Tree Recursion

Explanation of linear and tree recursion

When a recursive function makes only one recursive call during each step, it is known as linear recursion. It then moves linearly from one step to the next while simultaneously reducing the size of the original problem.

On the other hand, tree recursion is when a recursive function can make multiple recursive calls in each step. It results in a visual representation similar to a tree, where the branches signify multiple subsequent calls generated by every recursive call.

Examples of each type of recursion

Linear Recursion

int linearRecursion(int n) {
if (n == 0) {
return 0;
}
return n + linearRecursion(n - 1); // Single recursive call
}

Here we have used the ‘linearRecursion’ function to determine the sum of all natural numbers ranging from ‘n’ to 1. As quite visible, it has made a single recursive value of ‘n - 1’ in each step while moving towards ‘n == 0’, which is the base case.

Tree Recursion

void treeRecursion(int n) {
if (n > 0) {
printf("%d\n", n);
treeRecursion(n - 1); // First recursive call
treeRecursion(n - 2); // Second recursive call
}
}

Here, we have used the ‘treeRecursion’ function to generate a tree-like structure of the recursive calls. As quite visible, it has made two recursive calls of ‘n - 1’ and ‘n - 2’, value, each. Thus, a branching pattern has been created in the recursive calls, so we refer to this as tree recursion.

Differences between the two types of recursion

The table below cites the main differences between linear recursion and tree recursion.

Advantages and Disadvantages of Recursion Function in C

While the advantages of using recursion in C are many, there are quite a few downsides to it as well. Let’s explore how.

Comparison of recursion with iterative loops

Before delving into the details of when you should not use recursion, let’s first understand the key points that differentiate recursion from iterative loops.

Advantages and disadvantages of using recursion

Advantages

Efficient Data Processing - One advantage of recursive functions is efficient data processing, allowing for effective data storage, retrieval, and navigation across complex data structures like trees and graphs.

Reduced Time and Space - By reducing the amount of code required to solve a problem, recursion saves up a lot of time and space. It tends to be more concise when compared to other non-recursive functions.

Disadvantages

Difficulty In Debugging - Recursive codes, at times, can be quite hard to understand and even harder to debug. This is because the flow of execution is not always straightforward, thus making it challenging for users to identify and rectify issues in the code exactly.

Memory Usage - Recursive functions can consume significant memory due to the creation of new stack frames with each function call. This can result in high memory usage, particularly when dealing with large input sizes or deep recursion levels.

Situations when recursion can be useful

Let’s explore a few instances where recursion can be efficiently implemented.

• Recursion can be extremely useful in problems involving nested structures or where it can be naturally broken down into smaller subproblems.
• Recursion is applicable in backtracking algorithms to explore all possible solutions through a series of choices and undo the same if they do not generate a valid result.
• Recursion can bear fruitful results when used in divide-and-conquer algorithms such as binary search, mergesort, or quicksort.

C Program Function to show Direct Recursion

Here is a small example of a C program function to display direct recursion in C factorial.

#include <stdio.h>
int factorial(int m) {
// Base case: factorial of 0 is 1
if (m == 0) {
return 1;
}
// Recursive case: multiply m with factorial of (m-1)
return m * factorial(m - 1);
}
int main() {
int number;
printf("Enter a number: ");
scanf("%d", &number);
// Call the factorial function
int result = factorial(number);
printf("Factorial of %d is %d\n", number, result);
return 0;
}

Here we have used the ‘factorial’ function to show direct recursion. To calculate the recursion in C factorial, we have multiplied the input ‘n’ with the factorial of ‘n - 1’. The function calls itself with a reduced value in each step until it reaches the base case, when ‘n’ equals 0. Following this, it terminates the recursion and returns 1.

The user is then asked to enter a number using the ‘main’ function, and the ‘factorial’ function is called with that number. It then displays the final result, highlighting the input number's factorial.

C Program Function to Show Indirect Recursion

Below is an example of a C program to help you understand indirect recursion.

#include <stdio.h>
// Forward declaration of the functions
void functionA(int n);
void functionB(int n);
void functionA(int n) {
if (n > 0) {
printf("%d ", n);
functionB(n - 1); // Call functionB with n-1
}
}
void functionB(int n) {
if (n > 1) {
printf("%d ", n);
functionA(n / 2); // Call functionA with n/2
}
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
printf("Sequence of numbers: ");

// Call functionA to start the sequence
functionA(num);
return 0;
}

Here, we have used two functions, ‘functionA’ and ‘functionB’, to display indirect recursion. ‘functionA’ prints the number ‘n’ and then calls ‘functionB’, with value ‘n-1’. Similarly, ‘functionB’ prints a number ‘n’, then calls ‘functionA’ with the value ‘n/2’. Thus, a sequence of numbers is generated based on the specific pattern.

Following this, the user is asked to enter a number using the ‘main’ function’. ‘functionA’ is then called to start the sequence. Ultimately, the sequence of numbers based on the indirect recursion pattern will be displayed.

Best Practices

To write efficient recursive functions in C, consider factors like the problem's recursive nature and the C language's limitations. Here are some ways to ensure efficiency in your recursive functions.

• Define correct and reachable base cases to avoid any chances of infinite recursion.
• Break down the problem into smaller units efficiently to generate a more manageable recursive solution
• Store intermediate results in data structures and reuse them as and when required.
• Be careful about memory usage, and try to minimise it as much as possible.
• Select appropriate data types for function parameters to avoid unnecessary data transfer.
• Conduct frequent tests with varied input values to avoid incorrect output or unexpected errors.

Best practices for organising complex recursive functions

Organising complex recursive functions in C is crucial for improving code readability and understanding. Here are a few tips and tricks to help you with the same.

• Clearly define the function signature, including the return type, parameters, and function name.
• Maintain clear documentation and use comments wherever necessary to explain the recursive logic.
• Generate descriptive variable names to improve code understanding.
• Implement necessary debugging techniques to rectify any errors that might arise.

Conclusion

In conclusion, recursion in C offers numerous benefits, including debugging code, facilitating algorithmic thinking, and handling complex data structures. However, it is crucial to understand when to appropriately utilise recursion in order to maximise its advantages.

Additionally, if you wish to receive further information about the different aspects of programming, check out upGrad’s Graduate Certificate Programme In Data Science to explore the in-depth programming world under the expanding domain of data science.

FAQs

Q1: What are the different types of recursion in C?

There are primarily two types of recursion in C- Direct and indirect recursion. The former occurs when a function calls itself in a single-step recursive call. Indirect recursion occurs when a function calls itself in a two-step recursive call.

Q2: Can you state some of the applications of recursion in C?

Recursion has various applications. From computing factorial functions and powers of a number to drawing a type of fractal or solving Tower of Hanoi problems, recursion is widely used.

Q3: What are the advantages of recursion?

Recursion brings to the table a plethora of benefits. It increases code understandability and readability and can significantly reduce the time required to debug code.

Test your C programming skills with a Free Quiz

Start Quiz