Direct vs. Indirect Recursion

Direct Recursion

When a function calls itself directly within its own body then it is called direct recursion. 

Example:

int fun(int n) 
{
    if (n == 1)
        return 1;
    else 
        return 1 + fun(n-1); 
}

Indirect Recursion

In indirect recursion, a function calls another function which in turn call the original function. This creates a chain of function calls that eventually leads back to the original function.

Example:

int fun1(int n) 
{
    if (n == 1)
        return 1;
    else 
        return 1 + fun2(n-1); // calling fun2
}

int fun2(int n) 
{
    if (n == 1)
        return 1;
    else
        return 1 + fun1(n-1); // calling fun1
}

Practical Applications

Direct Recursion

Following are the applications of direct recursion which we already saw in our previous tutorials:

1. Finding the factorial of a number. 
2. Finding the nth Fibonacci number. 

And, there are many more applications of direct recursion.

Indirect Recursion

Program: check if a number is even or odd.

#include <stdio.h>

int odd(int);
int even(int);

int even(int n) 
{
    // Base case: 0 is even.
    if (n == 0)
        return 1;
    else 
        return odd(n-1); // calling odd
}

int odd(int n) 
{
    // Base case: 0 is not even
    if (n == 0)
        return 0;
    else
        return even(n-1); // calling even
}

int main()
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    
    // check if the number is even.
    if (even(n)) {
        printf("Number is even.");
    } else {
        printf("Number is odd.");
    }
    return 0;
}

Output:

Enter a number: 68
Number is even.

Explanation:

The program is using indirect recursion to check if a number is even or odd. Within the main() function, even() function is called. If the number is even then eventually the base case of the even() function will be true. If not, then the base case of the odd() function will be true. 

For example, consider that n is 2. The even() function is called. The base case is not true as n is not equal to 0, therefore the odd() function is called with value 1. In the odd() function also the base case is not true, so the even() function is called, and this time the base case condition is satisfied. This means the number is even, and that’s true 😎

Now, you can easily verify the program on your own by providing different values of n to the even() function.

This is one application of indirect recursion, but there are many use cases where indirect recursion makes more sense and works correctly. 

Summary

• Direct recursion means a function calls itself within its own body. 
• Indirect recursion refers to a function calling another function which in turn calls the original function. 

Test Your Knowledge

#include <stdio.h>

void A(int);
void B(int);

void B(int n) {
    if (n > 0) {
        printf("%d ", n);
        A(n-1);
    }
}

void A(int n) {
    if (n > 1) {
        printf("%d ", n);
        B(n/2);
    }
}

int main() {
    A(4);
    return 0;
}

Your score is out of