Recursion

Recursion is a programming technique where a function calls itself to solve a problem. Think of it like looking into two mirrors facing each other - you see an infinite reflection of yourself! In programming, recursion breaks down complex problems into smaller, similar subproblems.

How Recursion Works

Every recursive function needs two essential components:

1. Base Case: A condition that stops the recursion (like the bottom of a staircase)
2. Recursive Case: The function calling itself with a modified parameter (like taking one step down the staircase)

Factorial Example

Let's understand recursion with the classic factorial example. The factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

For example:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 4! = 4 × 3 × 2 × 1 = 24
• 3! = 3 × 2 × 1 = 6

Notice the pattern? We can express factorial recursively:

• n! = n × (n-1)!
• Base case: 0! = 1 and 1! = 1

Here's how to implement factorial using recursion in C:

#include <stdio.h>

int factorial(int n) {
    // Base case: factorial of 0 and 1 is 1
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

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

How the Recursion Unfolds

Let's trace through factorial(5):

factorial(5) = 5 * factorial(4)
             = 5 * (4 * factorial(3))
             = 5 * (4 * (3 * factorial(2)))
             = 5 * (4 * (3 * (2 * factorial(1))))
             = 5 * (4 * (3 * (2 * 1)))
             = 5 * (4 * (3 * 2))
             = 5 * (4 * 6)
             = 5 * 24
             = 120

Key Points to Remember

• Always define a base case to prevent infinite recursion
• Make sure you're moving toward the base case with each recursive call
• Recursion uses the call stack, so too many recursive calls can cause stack overflow
• Some problems are naturally recursive (like tree traversal, fractals)
• Not all problems need recursion - sometimes iterative solutions are more efficient

Recursion vs Iteration

Here's the same factorial function using iteration for comparison:

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

Both approaches solve the same problem, but recursion often makes the code more readable and elegant for certain types of problems!