C Recursion

Recursion is when a function calls itself.

1. Basic Recursion

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

2. Fibonacci Sequence

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

3. Key Points

• Base case is essential to prevent infinite recursion
• Each recursive call uses stack space
• Some problems are naturally recursive (tree traversal, factorial, etc.)

4. Tail Recursion

int factorial_tail(int n, int acc) {
    if (n <= 1) {
        return acc;
    }
    return factorial_tail(n - 1, n * acc);
}