Indirect Recursion in C

Back to: C Tutorials For Beginners and Professionals

Indirect Recursion in C Language with Examples

In this article, I will discuss Indirect Recursion in C Language with Examples. Please read our previous article discussing Direct Recursion in C Language with Examples. At the end of this article, you will understand the following pointers:

1. What is Indirect Recursion?
2. Multiple Real-Time Examples to Understand Indirect Recursion in C Language
3. Advantages of Indirect Recursion in C Language
4. Disadvantages of Indirect Recursion in C Language
5. When Would We Use Indirect Recursion in C Language?

What is Indirect Recursion in C Language?

Indirect recursion in C language, or in programming in general, occurs when a function calls another function, which in turn calls the first function again. This creates a cycle of function calls, and it’s not as straightforward as direct recursion, where a function calls itself directly.

Indirect recursion can involve two or more functions. The recursive cycle continues until a base condition is met in one of the functions, which breaks the cycle and allows the stack of function calls to unwind. Here’s a simple example to illustrate indirect recursion in C:

void functionA(int n);

void functionB(int n) {
    if (n > 0) {
        printf("%d ", n);
        functionA(n - 1); // Call to functionA
    }
}

void functionA(int n) {
    if (n > 1) {
        printf("%d ", n);
        functionB(n / 2); // Call to functionB
    }
}

int main()
{
    // Calling functionA
    functionA(10); // This will start the indirect recursion
    return 0;
}

In this example, functionA and functionB are involved in indirect recursion. functionA calls functionB, which in turn calls functionA, and so on. The cycle of calls continues until the base condition in one of these functions is met (in this case, when n becomes 0 or 1), which stops the recursion.

Indirect Recursion Real-Time Examples in C Language

Indirect recursion occurs when a function calls another function, which calls the first function. This kind of recursion is less common than direct recursion but can be useful in certain scenarios. Here are some examples of indirect recursion in the C language:

Example: Mutual Recursion for Even and Odd Checking

This example uses two functions, isEven and isOdd, which call each other to determine if a number is even or odd.

#include <stdio.h>

// Forward declarations of functions
void printOdd(int n);
void printEven(int n);

// Function to print odd numbers
void printOdd(int n) {
    if (n <= 0) 
        return;
    printf("%d ", n);
    printEven(n - 1); // Indirect call to printEven
}

// Function to print even numbers
void printEven(int n) {
    if (n <= 0) 
        return;
    printf("%d ", n);
    printOdd(n - 1); // Indirect call to printOdd
}

int main() {
    int number = 10;
    printOdd(number);
    return 0;
}

Output: 10 9 8 7 6 5 4 3 2 1

Explanation:

• The program consists of two functions: printOdd and printEven.
• printOdd prints an odd number and then calls printEven.
• printEven prints an even number and then calls printOdd.
• This creates indirect recursion since printOdd and printEven call each other.
• The recursion terminates when the number becomes zero or negative.

Example: Mutual Recursion for Calculating Series

#include <stdio.h>

// Forward declarations of functions
int isEven(int n);
int isOdd(int n);

// Function to check if a number is even
int isEven(int n) {
    if (n == 0)
        return 1;
    else
        return isOdd(n - 1); // Indirect call to isOdd
}

// Function to check if a number is odd
int isOdd(int n) {
    if (n == 0)
        return 0;
    else
        return isEven(n - 1); // Indirect call to isEven
}

int main() {
    int number = 5;
    if (isEven(number))
        printf("%d is even\n", number);
    else
        printf("%d is odd\n", number);
    return 0;
}

Output: 5 is odd

Explanation:

• The program has two functions: isEven and isOdd.
• isEven returns 1 (true) if a number is even. Otherwise, it calls isOdd.
• isOdd returns 1 (true) if a number is odd. Otherwise, it calls isEven.
• This creates indirect recursion, as these functions call each other to determine if a number is even or odd.
• The recursion terminates when the number becomes zero.

Example: Mutual Recursion For Positive and Negative Number Checks

Two functions, isPositive and isNegative, use indirect recursion to check if a number is positive or negative.

#include <stdio.h>

int isPositive(int n);
int isNegative(int n);

int isPositive(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return isNegative(n - 1); // Indirect call to isNegative
}

int isNegative(int n) {
    if (n == 0)
        return 0;
    else if (n == -1)
        return 1;
    else
        return isPositive(n + 1); // Indirect call to isPositive
}

int main() {
    int num = -3;
    if (isPositive(num))
        printf("%d is positive.\n", num);
    else if (isNegative(num))
        printf("%d is negative.\n", num);
    else
        printf("%d is neither positive nor negative.\n", num);
    return 0;
}

Output: Segmentation fault

Advantages and Disadvantages of Indirect Recursion in C Language

Indirect recursion in C language, or mutual recursion, occurs when a function calls another function, which in turn calls the first function, creating a cycle. This method has its unique set of advantages and disadvantages.

Advantages of Indirect Recursion in C Language

• Natural Modeling of Certain Problems: Indirect recursion can naturally model certain problems where two or more states or processes alternately occur, such as in certain state machines or parsing complex grammatical structures.
• Clarity in Complex Algorithms: It can clarify and separate concerns by dividing complex algorithms into different functions, each handling a specific part of the task.
• Maintains State Separately: Each recursive function in the cycle can maintain its own state and variables, which can be advantageous for problems where maintaining separate states is beneficial.
• Elegance in Problem-Solving: For certain problems, indirect recursion can lead to more elegant and theoretically neat solutions than direct recursion or iterative approaches.

Disadvantages of Indirect Recursion in C Language

• Increased Complexity: Indirect recursion can make code more complex and harder to understand, especially for those not familiar with the concept. It can also make debugging more challenging.
• Stack Overflow Risk: Like direct recursion, indirect recursion carries the risk of stack overflow if the recursion depth is too large or the base case is not properly defined.
• Performance Overhead: Each recursive call involves overhead, such as saving the function’s state and setting up the stack for the call. This can lead to performance issues, particularly if the recursion depth is significant.
• Difficulty in Maintenance and Debugging: Tracing and maintaining code with indirect recursion can be more challenging than with direct recursion or iterative code, especially in complex systems.
• Potential for Infinite Recursion: If the base cases are not well-defined or the termination condition is not reached due to logical errors, it can result in infinite recursion, causing the program to crash or hang.
• No Tail Call Optimization: Tail call optimization is generally not applicable in cases of indirect recursion, potentially leading to inefficient use of stack space.

When Would We Use Indirect Recursion in C Language?

Indirect recursion in C, or in any programming language, occurs when a function calls another function, which in turn calls the first function, creating a cycle of function calls. This form of recursion is less common than direct recursion but can be useful in certain scenarios:

• Complex Logical Decomposition: Indirect recursion can be used when a problem’s logic can be naturally divided into alternating steps that are best expressed by separate functions. This can make each function simpler and focused on a specific task.
• State Machine Implementation: In scenarios where you’re implementing a state machine, and the transition from one state to another is best represented by different functions calling each other, indirect recursion can be a good fit.
• Alternating Recursive Tasks: If a problem involves two or more tasks that need to be done alternatingly, where each task is distinctly different and complex enough to warrant its own function, indirect recursion can be used.
• Simplifying Complex Algorithms: In some complex algorithms where different functions best handle different phases of the algorithm, indirect recursion can help organize and manage the code.

In the next article, I will discuss Nested Recursion in C Language with Examples. In this article, I explain Indirect Recursion in C Language with Examples. I hope you enjoy this article.