Types of Recursion

Recursion is a technique in which a function solves a problem by calling itself with smaller inputs. Depending on how the recursive calls are made, recursion can be classified into different types. Each type has its own behavior, efficiency, and use cases.

Types of Recursion

1. Direct Recursion
2. Indirect Recursion
3. Tail Recursion
4. Non-Tail Recursion
5. Linear Recursion
6. Binary Recursion
7. Multiple Recursion

1. Direct Recursion

Direct recursion occurs when a function calls itself directly within its own body.

In this type, the function contains a recursive call to itself, along with a base case to stop execution. The problem is reduced step by step until the base condition is reached.

• The function directly invokes itself.
• A base case is necessary to terminate recursion.
• Each call reduces the problem size.

Example

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Direct recursive call
}

Use Cases

• Factorial calculation
• Sum of natural numbers
• Power computation

2. Indirect Recursion

Indirect recursion occurs when two or more functions call each other in a cyclic manner.

Instead of calling itself directly, a function calls another function, which eventually calls the original function again.

• Involves multiple functions.
• Forms a cycle of function calls.
• Must include a base case to avoid infinite recursion.

Example

#include <stdio.h>

void isEven(int n);
void isOdd(int n);

void isEven(int n) {
    if (n == 0) {
        printf("Even\n");
        return;
    }
    isOdd(n - 1);
}

void isOdd(int n) {
    if (n == 0) {
        printf("Odd\n");
        return;
    }
    isEven(n - 1);
}

Use Cases

• Even–odd checking
• Problems involving alternating states
• Compiler design

3. Tail Recursion

A function is tail recursive if the recursive call is the last operation performed.

In tail recursion, no computation is left after the recursive call returns. This allows compilers to optimize the recursion into an iterative process.

• Recursive call is the final statement.
• No pending operations after the call.
• Can be optimized (Tail Call Optimization).
• Uses less memory.

Example

int factorialTail(int n, int acc) {
    if (n == 0) return acc; // Base case
    return factorialTail(n - 1, n * acc); // Tail recursive call
}

Use Cases

• Factorial calculation
• GCD computation
• Efficient recursive algorithms

4. Non-Tail Recursion

A function is non-tail recursive when operations remain after the recursive call.

Here, the recursive call is not the last step. The function must perform additional work after the recursive call returns.

• Recursive call is followed by further computation.
• Requires extra stack memory.
• Cannot be easily optimized.

Example

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1); // Multiplication after call
}

Use Cases

• Tree traversal
• Fibonacci sequence
• Sorting algorithms

5. Linear Recursion

Linear recursion occurs when a function makes only one recursive call per execution.

This type forms a straight chain of recursive calls, where each call leads to exactly one more call.

• Only one recursive call at each step.
• Uses linear stack space O(n)O(n)O(n).
• Simple and easy to understand.

Example

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

Use Cases

• Factorial
• Sum of numbers
• Printing sequences

6. Binary Recursion

Binary recursion occurs when a function makes two recursive calls in each step.

This creates a tree-like structure of calls, where each function splits into two further calls.

• Two recursive calls per step.
• Forms a branching structure.
• Higher time complexity.

Example

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2); // Two calls
}

Use Cases

• Fibonacci sequence
• Divide and conquer algorithms
• Tree problems

Drawback

• Repeated calculations
• Inefficient for large inputs

7. Multiple Recursion

Multiple recursion occurs when a function makes more than two recursive calls at each step.

This type expands into multiple branches at every step, leading to very high complexity.

• More than two recursive calls.
• Forms a multi-branch structure.
• Requires large memory and time.

Example

#include <stdio.h>

void multipleRec(int n) {
    if (n <= 0) return; // Base case

    printf("%d ", n);

    multipleRec(n - 1);
    multipleRec(n - 2);
    multipleRec(n - 3);
}

Use Cases

• Tower of Hanoi
• N-Queens problem
• Generating subsets

Drawback

• Exponential time complexity
• High memory usage

Comparison Table of Recursion Types

Conclusion

Different types of recursion provide different ways to solve problems depending on structure and requirements.

• Simpler problems → Linear or Direct recursion
• Efficient recursion → Tail recursion
• Complex branching problems → Binary or Multiple recursion

Understanding these types helps in selecting the most efficient and appropriate approach for solving computational problems using recursion.