Types of Recursions

Recursion is a technique in which a function calls itself to solve smaller instances of the same problem.

Different types of recursion exist, and each has its own properties, advantages, and use cases. Below is a detailed theoretical explanation of each type.

1. Direct Recursion

A function is said to have direct recursion when it calls itself directly within its body.

Characteristics:

• The function contains a base case to stop recursion.
• It directly calls itself with a modified argument.
• If improperly implemented, it may lead to infinite recursion and a stack overflow.

Use Cases:

• Factorial calculation
• Sum of natural numbers
• Power calculation

Example::

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

2. Indirect Recursion

In indirect recursion, two or more functions call each other in a cyclic manner.

Characteristics:

• Instead of a function calling itself, it calls another function that, in turn, calls the original function.
• The sequence of calls should lead to a base case to prevent infinite recursion.
• Can be difficult to debug due to multiple function calls.

Use Cases:

• Problems where decisions alternate between two cases (e.g., even-odd checking).
• Compiler design and mutual recursion problems.

Example:

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

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

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

3. Tail Recursion

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

Characteristics:

• No additional computation is performed after the recursive call.
• It allows for tail call optimization (TCO), where the compiler can optimize the recursion into an iterative form.
• Memory-efficient because it does not require additional stack frames.

Use Cases:

• Factorial calculation
• Greatest common divisor (GCD) calculation
• Tree traversal

Example:

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

Note: Unlike normal recursion, this function does not keep track of previous values in the stack.

4. Non-Tail Recursion

A recursive function is non-tail recursive if there are additional operations after the recursive call.

Characteristics:

• The recursive call is not the last statement.
• Requires extra memory to store intermediate results.
• Cannot be optimized into an iterative process.

Use Cases:

• Tree traversal (e.g., inorder, preorder, postorder)
• Fibonacci sequence calculation
• Merge sort, quick sort

Example:

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

Drawback: Uses extra stack space due to delayed computation.

5. Linear Recursion

A function is linearly recursive if it makes at most one recursive call in each execution.

Characteristics:

• The function follows a linear chain of recursive calls.
• Uses O(n) stack space.
• Simplifies breaking problems into smaller subproblems.

Use Cases:

• Factorial computation
• Sum of first N numbers
• Printing numbers from N to 1

Example:

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

6. Binary Recursion

A function is binary recursive if it makes two recursive calls at each step.

Characteristics:

• Forms a tree-like recursive structure.
• Uses O(2^n) stack space in worst-case scenarios.
• Slower than linear recursion due to multiple recursive calls.

Use Cases:

• Fibonacci sequence
• Divide and conquer algorithms (Merge Sort, Quick Sort)
• Tree traversals

Example:

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

Drawback: Very inefficient for large n due to repeated calculations.

7. Multiple Recursion

A function is multiple recursive if it makes more than two recursive calls at each step.

Characteristics:

• Forms a multi-branch recursive structure.
• Requires large stack space.
• Often seen in problems requiring multiple state evaluations.

Use Cases:

• Solving the Tower of Hanoi problem
• Computing all subsets of a set
• N-Queens problem

Example:

void multipleRec(int n) {
    if (n == 0) return; // Base case
    printf("%d ", n);
    multipleRec(n - 1); // First recursive call
    multipleRec(n - 2); // Second recursive call
    multipleRec(n - 3); // Third recursive call
}

Problem: Leads to exponential time complexity (O(3^n)) if not optimized.

Comparison Table of Recursion Types