Mastering Recursion

Recursion is when a function calls itself. It is a powerful conceptual tool for solving complex problems by breaking them into smaller, identical sub-problems. It is the language of Trees, Graphs, and Dynamic Programming.

1. The Two Pillars of Recursion

• Base Case: The "Exit Condition." Without this, you get a StackOverflowException as the stack runs out of memory.
• Recursive Step: Calling the function with a "smaller" version of the problem.

public int Factorial(int n) {
    if (n <= 1) return 1; // Base Case
    return n * Factorial(n - 1); // Recursive Step
}

2. The Call Stack

Every time a function calls itself, a new **Stack Frame** is added to the memory. If the recursion is 1 million levels deep, your app will crash. This is why we sometimes prefer **Iterative** (loop-based) solutions for simple problems.

4. Interview Mastery

Q: "What is 'Tail Call Optimization' and does C# support it?"

Architect Answer: "Tail Call Optimization occurs when the recursive call is the *very last* thing the function does. In theory, the compiler can reuse the current stack frame instead of adding a new one, making the recursion as fast as a loop. While the 64-bit JIT compiler in .NET DOES support this for certain IL patterns, it is not guaranteed. For critical, deep recursion, a senior dev should always consider using an explicit **Stack** object to simulate recursion in a safe, iterative way."