Types of Recursive Functions in C

Back to: C Tutorials For Beginners and Professionals

Types of Recursive Functions in C Language

In this article, I will discuss Types of Recursive Functions in C Language with Examples. Please read our previous article discussing How to Find the Time Complexity of a Recursive Function in C Language.

Types of Recursive Functions in C Language

In C programming, recursive functions can be categorized based on how they call themselves and handle recursion. Recursive functions in C language can be categorized based on their structure and the nature of the problems they solve. Here are some common types of recursive function programs in C:

• Direct Recursion: This is the most straightforward type of recursion where a function calls itself directly. Examples include calculating factorials, Fibonacci numbers, or summing a list of numbers.
• Indirect Recursion: In this type, a function calls another function, which in turn calls the first function. This creates a cycle of function calls. For example, Function A calls Function B, Function B calls Function A, and so on.
• Tail Recursion: If a recursive function call is the last thing executed inside the function (i.e., the call is in the “tail” position), it’s called tail recursion. In tail recursion, the function doesn’t have to do anything after returning from the recursive call. An example is a tail-recursive version of calculating factorial.
• Head (Non-Tail) Recursion: If the recursive call is not in the tail position, meaning the function does some operation after the recursive call returns, it’s non-tail recursion. Most simple recursive functions, like a standard factorial or Fibonacci calculation, are non-tail recursive.
• Nested Recursion: In this type, the recursive function call is made with a parameter that is itself a recursive call. These can be quite complex and are more of an academic interest. An example is a function where the parameter passed to the recursive call is itself a recursive call.
• Mutual Recursion: This is a form of indirect recursion where two or more functions are interdependent and call each other recursively. It’s a more complex form of recursion typically used in more advanced programming scenarios.
• Tree Recursion: A function makes multiple calls to itself in tree recursion. This is common in problems where different branches of computation need to be explored, such as generating the subsets of a set or exploring paths in a graph.
• Linear Recursion: This is a simpler form of recursion where the function makes a single recursive call at each level. Linear recursion is often more efficient and easier to understand than tree recursion.

Direct Recursion in C Language

Direct recursion occurs when a function calls itself directly. A classic example of direct recursion in C programming is a function to compute the factorial of a number. The factorial of a positive integer n (denoted as n!) is the product of all positive integers less than or equal to n. The factorial of 0 is defined as 1. Here’s a simple C program that demonstrates direct recursion by calculating the factorial of a given number:

#include <stdio.h>

// Function to calculate the factorial of a number
int factorial(int n) {
    if (n == 0) {
        // Base case: factorial of 0 is 1
        return 1;
    } else {
        // Direct recursion: the function calls itself
        return n * factorial(n - 1);
    }
}

int main() {
    int number = 5; // Change this value to compute the factorial of a different number
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

In this program, the factorial function is directly recursive because it calls itself to compute the factorial of n−1. This recursion continues until it reaches the base case where n is 0. At that point, the function returns 1, and the recursive calls start unwinding, multiplying the numbers as they return.

Indirect Recursion in C Language

Indirect recursion occurs when a function is called not by itself directly but through another function. In other words, one function calls a second function, which in turn calls the first function, creating a cycle. This type of recursion can be used in various scenarios, especially when two distinct operations need to alternate in a recursive process.

Here’s an example of an indirect recursion program in C. In this example, two functions functionA and functionB call each other alternatively:

#include <stdio.h>

void functionB(int n); // Forward declaration

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

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

int main() {
    functionA(20);
    return 0;
}

In this program, functionA and functionB are mutually recursive. functionA starts with a positive integer n and calls functionB with n-1. functionB, in turn, calls functionA with n/2. This alternation continues until the base conditions in functionA and functionB are met. The output of this program will be a sequence of numbers showing how the control moves between these two functions.

Tail Recursion in C Language

Tail recursion is a special recursion case where the recursive call is the last operation in the function. In tail recursion, there is no need to keep track of the previous state once a recursive call is made. This can lead to optimizations like reusing stack frames and making tail recursion as efficient as iteration in some cases. Here’s an example of a tail-recursive function in C for calculating the factorial of a number:

#include <stdio.h>

// Tail recursive helper function
long factorial_helper(int n, long accumulator) {
    if (n == 0) {
        return accumulator;
    } else {
        return factorial_helper(n - 1, n * accumulator);
    }
}

// Wrapper function for factorial
long factorial(int n) {
    return factorial_helper(n, 1);
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    // Check for negative input
    if (number < 0) {
        printf("Factorial of a negative number doesn't exist.\n");
    } else {
        printf("Factorial of %d = %ld\n", number, factorial(number));
    }

    return 0;
}

In this program:

• A factorial_helper function is defined to implement the tail recursion. It takes two arguments: the current number n and an accumulator that carries the result of the factorial calculation so far.
• The base case checks if n is 0. If so, it returns the accumulator, which holds the final result.
• The function passes n – 1 and n * accumulator in the recursive call. Each call’s current state is updated, and no additional computation is needed after the recursive call.
• The factorial function is a wrapper that initiates the recursion with an accumulator value of 1.

Head Recursion in C Language

Head recursion is a specific type of recursion where the recursive call occurs at the beginning of the function before any other processing. This means the function performs its operations after the recursive call has returned. In head recursion, the calculations or actions happen during the unwinding phase of the recursion (when the recursive calls are returning). Here’s an example of a head recursion program in C:

#include <stdio.h>

// A head recursive function
void headRecursion(int n) {
    if (n > 0) {
        headRecursion(n - 1);  // Recursive call at the beginning
        printf("%d ", n);      // Action performed after the recursive call
    }
}

int main() {
    headRecursion(5);
    return 0;
}

In this program, the function headRecursion is a head recursive function. It first calls itself with a decremented value of n, only after the recursive calls have reached the base case (n > 0). It starts to print the numbers during the unwinding phase. This is the opposite of tail recursion, where the action happens before the recursive call.

The output of this program will be 1 2 3 4 5, as the function prints the numbers on its way back from the deepest point of recursion.

Tree Recursion in C Language

Creating a tree recursion program in C involves designing a function that makes multiple recursive calls within its body. Here’s a simple example to illustrate this concept using a function that calculates the sum of natural numbers up to a given number but in a tree-recursive manner.

#include <stdio.h>

// Function declaration
int treeRecursiveSum(int n);

int main() {
    int number, result;

    printf("Enter a number: ");
    scanf("%d", &number);

    result = treeRecursiveSum(number);

    printf("Tree recursive sum of %d is %d\n", number, result);

    return 0;
}

// Function to calculate sum in a tree recursive way
int treeRecursiveSum(int n) {
    if (n <= 1) {
        return n;
    } else {
        return treeRecursiveSum(n - 1) + treeRecursiveSum(n - 2);
    }
}

In this program:

• The treeRecursiveSum function takes an integer n.
• If n is less than or equal to 1, it returns n (base case).
• Otherwise, it makes two recursive calls, treeRecursiveSum(n – 1) and treeRecursiveSum(n – 2), and returns their sum.

This is a simple example of tree recursion, where each call branches into further calls, forming a tree-like structure in the call stack. Remember, tree recursion can be inefficient for certain problems involving repeated calculations. This example, for instance, is not the most efficient way to sum natural numbers but serves well to demonstrate the concept of tree recursion.

Mutual Recursion in C Language

Mutual recursion occurs when two or more functions call each other in a cycle. This can be particularly useful for problems where the solution can be broken down into alternating tasks that are best solved by different functions. A classic example of mutual recursion is determining whether a number is even or odd, with each function calling the other to handle the next lower number until it reaches a base case. Here is a simple program in C that demonstrates mutual recursion for checking if a number is even or odd:

#include <stdio.h>

// Forward declarations are necessary for mutual recursion
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; // 0 is even
    else
        return isOdd(n - 1); // If not 0, check if the previous number is odd
}

// Function to check if a number is odd
int isOdd(int n) {
    if (n == 0)
        return 0; // 0 is not odd
    else
        return isEven(n - 1); // If not 0, check if the previous number is even
}

int main() {
    int number;
    printf("Enter a number: ");
    scanf("%d", &number);

    if (isEven(number))
        printf("%d is even.\n", number);
    else
        printf("%d is odd.\n", number);

    return 0;
}

In this program, isEven and isOdd call each other. When you run the program, it asks for a number input. It then uses the mutual recursion between isEven and isOdd to determine if the number is even or odd. This demonstrates how mutual recursion can be implemented in C.

Linear Recursion in C Language

A linear recursion program in C is characterized by a function that makes a single recursive call within each invocation. This kind of recursion is straightforward and often used for simple problems. A classic example of a linear recursive program is calculating the factorial of a number. Here’s how you can implement it in C:

#include <stdio.h>

// Function to calculate factorial using linear recursion
long factorial(int n) {
    if (n == 0) { // Base case
        return 1;
    } else {
        return n * factorial(n - 1); // Recursive call
    }
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    // Check for negative input
    if (number < 0) {
        printf("Factorial of a negative number doesn't exist.\n");
    } else {
        printf("Factorial of %d = %ld\n", number, factorial(number));
    }

    return 0;
}

In this program:

• The factorial function is called from the main. If the input number is 0 (the base case), it returns 1 because the factorial of 0 is 1.
• For any other number, the function calls itself with n – 1. This continues until it reaches the base case.
• Each function call waits for the result of its recursive call before it can return its result, forming a linear chain of function calls.
• The program also includes a check for negative inputs since factorials for negative numbers are undefined.

Nested Recursion Program in C

Nested recursion is a form of recursion where a recursive function makes a recursive call with a parameter that is itself a recursive call. It’s a more complex and less common form of recursion due to its intricate calling pattern. Here’s a simple example of a nested recursion program in C:

#include <stdio.h>

// Function with nested recursion
int nestedRecursion(int n) {
    if (n > 100) {
        return n - 10;
    }
    return nestedRecursion(nestedRecursion(n + 11));
}

int main() {
    int result, number = 95;
    result = nestedRecursion(number);
    printf("Result: %d\n", result);
    return 0;
}

In this program, the nestedRecursion function is a nested recursive function. When nestedRecursion is called with a value less than or equal to 100, it makes a recursive call with nestedRecursion(n + 11) as the argument. This causes the function to recurse within its own recursion, creating a nested effect.

This kind of recursion can lead to quite complex execution patterns and can be more difficult to analyze than straightforward recursion. It’s often used in more advanced algorithms and mathematical computations. Remember that nested recursion can consume a lot of stack space and might lead to a stack overflow if not carefully managed, especially for large input values or deep recursion levels.

In the next article, I will discuss Tail and Head Recursion in C Language. I explain the Types of Recursive Functions in C Language in this article. I hope you enjoy this article on types of recursive functions in C Language. Please give your feedback and suggestions about this article.