🔁 Understanding Recursion in C – With Real Examples

Recursion is when a function calls itself to solve a problem. It's one of the most powerful (and elegant) tools in C programming—but often misunderstood.

In recursion, a function solves a small part of the problem and passes the rest back to itself.

🧠 When to Use Recursion?

Recursion is ideal when a problem can be broken down into smaller instances of the same problem — like factorials, Fibonacci numbers, or finding GCD.

📘 Example 1: Factorial Using Recursion

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

Input: 5
Output: 120

📘 Example 2: Sum of Natural Numbers

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

Input: 5
Output: 15 (1 + 2 + 3 + 4 + 5)

📘 Example 3: GCD (Greatest Common Divisor)

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Input: 48 and 18
Output: 6

📘 Example 4: Fibonacci Sequence

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

Input: 6
Output: 8 (0, 1, 1, 2, 3, 5, 8)

⚠️ Recursive Pitfalls

• Each recursive call adds to the call stack. Too many calls = stack overflow.
• Always define a base case or the function will call itself forever!
• Recursion is elegant but sometimes inefficient compared to loops (especially in Fibonacci).

✅ When Recursion Makes Sense

• Problems with branching (like trees, graphs, DFS)
• Breaking a big task into smaller subproblems
• Elegant one-liner solutions (like factorial, sum, GCD)

🎯 Conclusion

Recursion is not magic—it's just a way to solve problems by solving smaller pieces. With clear base cases and correct logic, recursive functions can be both beautiful and powerful. Practice the examples above, visualize the calls, and you'll become a recursion master in no time.