Types of Recursion in C: Syntax & Examples

Published: 20 Aug 2025 | Reading Time: 3 min read

Overview

Recursion is a fundamental technique in programming whereby a function calls itself. It is highly effective for solving problems that can be expressed as smaller, like sub-problems. More specifically, recursion finds its application in C programming in calculating factorials, generating Fibonacci series, tree traversal, etc. This article will discuss types of recursion, syntax, examples, time and space complexities, and methods to use recursion effectively in the language C.

Table of Contents

What is Recursion?

Recursion occurs when a function calls itself directly or indirectly to solve a problem. It is a method used to divide complex problems into simpler sub-problems by resolution. A recursive function generally comprises two components:

How Recursion Works

Types of Recursion

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)

Difference Between Recursion and Iteration

Here are the key differences for recursion and iteration:

Recursion Iteration
Recursion calls on a function all within itself so as to reduce the problem into its simple sub problems. Iteration will run a set of instructions called a loop.
It often more concise and faster for complex problems. Can be more straightforward and efficient.
Higher memory usage due to stack frames for each call. Lower memory usage as no stack frames are created.
Can be harder to debug and understand. It is generally easier to debug and understand.
Risk of stack overflow if base case is not reached. Risk of infinite loop if loop condition is wrong.
Ideal for problems that break down into smaller sub-problems. Ideal for repeating tasks or iterating over collections.
May be slower due to overhead. Can be more efficient in terms of time and space.
Can result in higher complexity, especially for large problems. Its design often simpler and more predictable in structure.

Advantages of Recursion in C

Here are the advantages of recursion in C:

Disadvantages of Recursion in C

Here are the disadvantages of recursion in C:

Conclusion

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.

Frequently Asked Questions

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:

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.

Related Articles