C - recursion in C

1. What is Recursion?

Recursion is when a function calls itself, either:

• Directly (function calls itself)

• Indirectly (function A calls B, which calls A again)

It’s often used for problems that can be broken down into smaller, similar subproblems.

2. Basic Structure of a Recursive Function

A recursive function has two key parts:

1. Base case → Stops the recursion (prevents infinite loop)

2. Recursive case → Function calls itself with a smaller/simpler problem

General pattern:

return_type function_name(parameters) {
    if (base_condition) {
        // stop recursion
        return base_value;
    } else {
        // recursive call
        return function_name(modified_parameters);
    }
}

3. Example: Factorial

#include <stdio.h>

int factorial(int n) {
    if (n == 0) // base case
        return 1;
    else
        return n * factorial(n - 1); // recursive case
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

How it works:

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
...
= 5 * 4 * 3 * 2 * 1

4. Example: Fibonacci Sequence

#include <stdio.h>

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

int main() {
    for (int i = 0; i < 10; i++)
        printf("%d ", fibonacci(i));
    return 0;
}

5. Indirect Recursion

#include <stdio.h>

void funcA(int n);
void funcB(int n);

void funcA(int n) {
    if (n > 0) {
        printf("%d ", n);
        funcB(n - 1);
    }
}

void funcB(int n) {
    if (n > 1) {
        printf("%d ", n);
        funcA(n / 2);
    }
}

int main() {
    funcA(10);
    return 0;
}

6. Advantages

• Elegant and closer to mathematical definitions

• Reduces code complexity for problems like:

  • Tree/graph traversal

  • Divide-and-conquer algorithms (Merge Sort, Quick Sort)

  • Backtracking problems (Sudoku, N-Queens)

7. Disadvantages

• More memory usage (each call stores data on the stack)

• Can be slower due to function call overhead

• Risk of stack overflow if recursion is too deep or base case is wrong