Types of Recursion in C: Syntax & Examples

There are various types of recursion in C. Each has its own structure and use cases, such as:

1. Direct Recursion

Direct recursion occurs when a function calls itself directly within its body. The function continues calling itself until a termination condition (or base case) is met.

Syntax

void functionName() {
    // some code
    functionName();  // Function calls itself
    // some more code
}

Example

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d", num, factorial(num));
    return 0;
}

Output

Factorial of 5 is 120

Explanation

In the above program, the factorial() function calls itself directly to calculate the factorial of a number. The recursion continues until it hits the base case, where n == 0, returning 1.

Time Complexity: O(n)

Space Complexity: O(n)

2. Indirect Recursion

Indirect recursion occurs when one function calls another function, which then calls the first function and reaches some sort of cycle. This recursion continues to call itself until some termination condition is met.

Syntax

void function1() {
    // some code
    function2();  // Calls function2()
}

void function2() {
    // some code
    function1();  // Calls function1() again
}

Example

#include <stdio.h>

int num = 1;

void odd() {
    if (num <= 10) {
        printf("%d ", num + 1);  
        num++;
        even();  // Calls even function
    }
}

void even() {
    if (num <= 10) {
        printf("%d ", num - 1);
        num++;
        odd();  // Calls odd function
    }
}

int main() {
    odd();  // Initial function call
    return 0;
}

Output

2 1 4 3 6 5 8 7 10 9

Explanation

In this program, the method odd() calls the method even(), which then calls the odd() method again. This gives rise to an indirect recursion cycle, printing alternating numbers till the variable num exceeds 10.

Time Complexity: O(n)

Space Complexity: O(n)

3. Tail Recursion

Tail recursion is a type of recursion where the calling of the function is the last operation in the function. It hence permits compiler optimization, memory-saving, and eliminating stack overflow.

Syntax

void functionName(int n) {
    if (n == 0) 
        return;
    else
        functionName(n - 1);  // Recursive call is the last operation
}

Example

#include <stdio.h>

void printNumbers(int n) {
    if (n == 0) 
        return;  // Base case
    else
        printf("%d ", n);  // Prints the number
    printNumbers(n - 1);  // Tail recursion
}

int main() {
    printNumbers(5);  // Calls function to print numbers from 5 to 1
    return 0;
}

Output

5 4 3 2 1

Explanation

In the printNumbers() function, the recursive call to printNumbers(n-1) is the last statement. Thus, it is tail recursion. The function continues calling itself until n==0.

Time Complexity: O(n)

Space Complexity: O(1)

4.  Non-tail Recursion

The non-tail recursion is also known as head recursion, the recursive call is the first step in the function and any operations are performed only when the function starts returning from the recursive calls.

Syntax

void functionName(int n) {
    if (n > 0) {
        functionName(n - 1);  // Recursive call first
        // Perform operation after the recursive call
    }
}

Example

#include <stdio.h>

void printNumbers(int n) {
    if (n > 0) {
        printNumbers(n - 1);  // Recursive call first
        printf("%d ", n);  // Prints after recursion
    }
}

int main() {
    printNumbers(5);  // Prints numbers from 1 to 5
    return 0;
}

Output

1 2 3 4 5

Explanation

In this program, the function printNumbers() first called itself recursively. After reaching the base condition, it prints numbers while unwinding the recursion stack.

Time Complexity: O(n)

Space Complexity: O(n)

5. Linear Recursion 

Linear recursion occurs when a function calls itself once per execution, and the number of recursive calls grows linearly with the size of the input problem.

Syntax

void functionName(int n) {
    if (n == 0)
        return;
    functionName(n - 1);  // A single recursive call
}

Example

#include <stdio.h>

int findMax(int arr[], int n) {
    if (n == 1) 
        return arr[0];
    return (arr[n - 1] > findMax(arr, n - 1)) ? arr[n - 1] : findMax(arr, n - 1);  // Linear recursion
}

int main() {
    int arr[] = {4, 8, 15, 16, 23, 42};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum number is: %d", findMax(arr, n));
    return 0;
}

Output

Maximum number is: 42

Explanation

The findMax() function finds a maximum in an array by making a single recursive call in every execution. It compares the current element with the largest value returned from a recursive call on the rest of the elements in the array.

Time Complexity: O(n)

Space Complexity: O(n)

6. Tree Recursion

Tree recursion occurs when a function makes more than one recursive call each time it is called, thus creating a branching structure. Examples of such recursive problems include a computation of Fibonacci numbers.

Syntax

void functionName(int n) {
    if (n > 1) {
        functionName(n - 1);  // First recursive call
        functionName(n - 2);  // Second recursive call
    }
}

Example

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // Tree recursion
}

int main() {
    int n = 6;
    printf("Fibonacci number at position %d is: %d", n, fibonacci(n));
    return 0;
}

Output

Fibonacci number at position 6 is: 8

Explanation

In the fibonacci() function, each recursive call makes two further calls, which ultimately results in a tree-like structure of recursion. This is a classic example of tree recursion.

Time Complexity: O(2^n) 

Space Complexity: O(n)

Here are the key differences for recursion and iteration

Here are the advantages of recursion in C:

• Recursion very often leads to simpler coding. This is especially true for problems such as the Tower of Hanoi, which have a recursive structure.
• Recursion is best suited for solving problems like tree traversals or dynamic programming problems, where the solution is elegantly recursive.
• Recursion provides the chance to have a smaller code, unlike loops, which tend to be a bit longer in coding.
• They are most effective where trees, stacks, and graphs come into the picture.
• A recursive solution can be more elegant and easier to analyze in dealing with a complex problem.

Here are the disadvantages of recursion in C:

• Recursive functions run slower than their non-recursive counterparts because of overhead.
• Recursion takes a lot of memory because every recursive call takes up stack space to store intermediate results.
• Recursive functions may be difficult to grasp by anyone not fundamentally acquainted with the concept.
• In some cases, recursion may prove less efficient in time and space than iterative solutions.
• If recursion is not properly implemented, a large number of recursive calls can grow beyond the stack size limit, resulting in memory issues.

In conclusion, types of recursion in C is one of the most powerful techniques that can be used to break a problem down into smaller parts. It reduces the complexity of the problem-multiplication functions, tree traversals, factorials, and Fibonacci sequences-into a more simple, cleaner-to-read code. However, it implies inefficient time and memory use when utilized in deep recursive calls or tree recursion. Tail recursion can be optimized and efficient in the use of memory. Depending on the problem, sometimes recursion is a more suitable way of solving it, while iteration proves to be better. Knowing the types of recursion allows one to choose the most suitable method of solving a problem.

1. How many types of recursion are there in C?

There are different types of recursion in C; the commonly used types are classified into:

• Direct Recursion
• Indirect Recursion
• Tail Recursion
• Non-Tail Recursion
• Linear Recursion
• Tree Recursion

2. What is Type Recursion?

The term ''type recursion'' is not a common name in programming; however, it might be used to refer to the common types of recursion that describe how a function calls itself in different manners based on its structure. The types are direct, indirect, tail, non-tail, linear, and tree recursion.

3. Why space complexity is less in case of loop ?

In case of loops, space complexity is less where loops don't create new stack at every iteration. They use a fixed amount of memory for variables like loop counters, whereas recursion has a stack overhead because space is allocated for each function call. In loops, memory is reused with space complexity held constant at O(1). Where recursion is concerned, space complexity will be O(n), due to stack overhead.

4. What is the difference between direct and Indirect Recursion?

• Direct Recursion

When a function calls itself from within, it's termed simple/direct recursion. The function directly calls itself to solve smaller subproblems.

• Indirect Recursion

Indirect recursion occurs when one function calls another function, which, in turn, calls the first function, forming a cycle of function calls. This gives rise to an indirect chain of recursion between both functions.