Recursion in C Programming

Recursion in C is a powerful programming method or technique by which you can solve smaller and repetitive parts of a problem easily, where a function calls itself. It has various applications, such as solving problems in data structure, simplifying complex tasks, or reversing a string; thus, understanding recursion is important for writing clean, simple, readable, and modular code. In this article, we will discuss what recursion is in C, its syntax, types, working, examples, advantages, and disadvantages.

Table of Contents:

• What is Recursion in C?
• Syntax of Recursion in C
• How does Recursion in C work?
• Types of Recursion in C
  1. Direct Recursion
  2. Indirect Recursion
• Examples of Recursion in C
• Advantages of Recursion
• Disadvantages of Recursion
• Conclusion

What is Recursion in C?

Recursion in C is a programming technique in which a function calls itself to solve the smaller instances of a problem. The recursion has two main parts: a base case that stops it, and a recursive case where the function calls itself. Each recursive call moves the problem closer to the base case. 

Recursion is commonly used in various programming tasks such as factorials, Fibonacci series, and tree traversals. It also provides us with a clear and concise way to solve various types of problems that have a repetitive nature or nested structure. Also, performing the recursion many times in the same program can lead to a stack overflow if it is not handled properly.

Syntax of Recursion in C

The syntax of recursion in C programming is:

return_type function_name(parameters) {
    if (base_condition)
        return value;  // Base case
    else
        return function_name(modified_parameters);  // Recursive call
}

This is the basic syntax of recursion or a recursive function in C, which checks if there is a base condition to stop the process, and if the condition is not met, then it calls itself with the modified parameters. The process continues until the base condition is true.

How does Recursion in C work?

Here is a step-by-step explanation of how recursion works:

Step 1: At first, the recursive function is called with a particular argument.

Step 2: Then, the function checks whether the base case or base condition is true or not to stop the recursion.

Step 3: If the base case is false, the function calls itself with the modified parameters, which means that the recursive case is executed.

Step 4: Then, a new call is added to the stack, and each recursive call is stored in the function call stack.

Step 5: Now, when the base case is met by a recursive call, it returns a value.

Step 6: Each recursive call resumes and returns its result until the original call is completed.

Here is a flowchart that will help you understand visually how recursion works.

Let’s understand the working of recursion in C with an example of finding factorial.

Output:

In the above example, we have to find the factorial of 4, and here is its step-by-step execution:

1. factorial(4) -> not base case -> returns 4 * factorial(3)
2. factorial(3) -> not base case -> returns 3 * factorial(2)
3. factorial(2) -> not base case -> returns 2 * factorial(1)
4. factorial(1) -> not base case -> returns 1 * factorial(0)
5. factorial(0) -> base case -> returns 1

Now the returned results are:

• factorial(1) = 1 × 1 = 1
• factorial(2) = 2 × 1 = 2
• factorial(3) = 3 × 2 = 6
• factorial(4) = 4 × 6 = 24

Finally, “Factorial of 4 is 24” is printed to the console.

Types of Recursion in C

There are two types of recursion in C: Direct and Indirect Recursion.

1. Direct Recursion

Direct recursion occurs when a function calls itself directly within its own body. It continues to call itself until a base condition is met. This is the simplest form of recursion used in many common problems like factorial and Fibonacci. 

Syntax of Direct Recursion in C:

return_type function_name(parameters) {
    if (base_condition)
        return value;  // Base case
    else
        return function_name(modified_parameters);  // Direct recursive call
}

Example:

Output:

The above program shows how the direct recursion method is used to print the numbers from 5 to 1 in descending order by calling the printDescending() function repeatedly with decreasing values of n. The recursion stops when n reaches 0, and then the numbers are printed to the console.

2. Indirect Recursion

Indirect recursion occurs when the function calls another function, and that second function calls back the first function. Due to this, a recursive loop is created between two or more functions. It is less common than direct recursion, but it is useful in some logic-based problems.

Syntax of Indirect Recursion in C:

void functionA(int n) {
    if (base_condition)
        return;
    // some code
    functionB(modified_value);  // functionA calls functionB
}

void functionB(int n) {
    if (base_condition)
        return;
    // some code
    functionA(modified_value);  // functionB calls functionA
}

Example:

Output:

The above program shows how the indirect recursion method is used, where “functionA” prints numbers from 5 to 1 by calling “functionB”, and “functionB” calls “functionA” back, continuing the recursion until n becomes 0.

Examples of Recursion in C

Here are a few examples of recursion in C:

1: Find the Fibonacci Series (First N Terms) Using Recursion

Output:

The above program shows that recursion is used to return the first 10 terms of the Fibonacci series, where each term is the sum of the two preceding numbers. Then, it calls the “fibonacci” function recursively for each term from 0 to 9, and as a result, the series “0 1 1 2 3 5 8 13 21 34” is printed to the console.

2: Find the Sum of Natural Numbers Using Recursion

Output:

The above program shows how recursion is used to calculate the sum of the first 10 natural numbers. The sum(n) function adds the current number n to the sum(n-1) until n reaches the base case (n == 0), and then the result “Sum of first 10 natural numbers is 55” is printed to the console.

3: Reverse a String Using Recursion

Output:

The above code shows how recursion is used to reverse a string. The recursive function “void reverse()” first reaches the end of the string using recursion, and then prints each character while returning from the recursive calls. And, finally, the reversed string “olleh” is printed to the console.

4: GCD (Greatest Common Divisor) Using Recursion

Output:

The above program shows how recursion is used to find the GCD(greatest common divisor) of two numbers using a recursive function based on the Euclidean algorithm. The recursive function “gcd()” calls “gcd(b, a%b)” until b becomes 0, at which point a becomes the GCD, where a=48 and b=18. Then, at last, “GCD of 48 and 18 is 6” is printed to the console.

5: Power of a Number Using Recursion

Output:

The above program shows how recursion is used to calculate the power of a number. In the program, the recursive function multiplies the base by itself exp times, and thus reduces the exponent by 1 on each recursive call until it reaches 0, where it returns 1.

Advantages of Recursion

1. Recursion helps to simplify complex problems by breaking them into smaller and easier sub-problems.
2. It makes the code or program cleaner, shorter, and more readable.
3. Recursion works smoothly with data structures such as trees and graphs.
4. It is good to use with algorithms such as QuickSort and Merge Sort.
5. It reduces the need for manual stack management in various tasks.
6. Recursion is also helpful in solving problems like the Tower of Hanoi or the N-queens.

Disadvantages of Recursion

1. Recursion or recursive functions use more memory because each call is stored on the call stack.
2. If the infinite recursion occurs when the base case is missing, it will lead to the program crashing.
3. Recursion is slower than iteration due to function call overhead.
4. In large input sizes, deep recursion may lead to a stack overflow.
5. A program using recursion is harder to understand and debug, especially for beginners.
6. Recursive solutions can be less efficient without optimization.

Conclusion

Recursion in C is an extremely useful method in programming that simplifies complex problems by recursively breaking them into simpler sub-problems. Programmers can write a cleaner and more logical implementation of the program using recursion. Common applications of recursion include calculating the factorial of a number, generating the Fibonacci series, and programming tasks (tree traversal), etc. Programmers must be careful when using recursion, as an application that often uses a lot of memory and tends to overflow the stack is a recursion-heavy application. A good understanding of the strengths and weaknesses of recursion can help one write a program that is not only efficient but also easily maintainable in the future.

Recursion in C Programming – FAQs