Recursion is a programming technique where a function calls itself to solve a smaller version of the same problem. It is the foundation of many complex algorithms (Trees, Graphs, DP).

Think of Russian Nesting Dolls (Matryoshka):

1. You want to reach the tiny prize inside the smallest doll.
2. You open the big doll. Inside is a slightly smaller doll.
3. You repeat the process: "Open the doll".
4. You stop when you reach the smallest doll that doesn't open. (This is the Base Case).
5. Only then can you start putting the dolls back together.

---

The Three Rules of Recursion

1. The Base Case: When to stop. Without this, you get a Stack Overflow.
2. The Recursive Step: How to break the problem into a smaller piece.
3. The Leap of Faith: Trust that your function works for the smaller piece. Don't try to trace everything in your head!

Complexity Analysis

• Time: Usually $O(\text{branches}^{\text{depth}})$. For factorials, it's $O(n)$. For Fibonacci, it's $O(2^n)$.
• Space: $O(\text{depth})$ due to the call stack! Every call takes up a new frame in memory.

---

javascript Standard
/**
 * Factorial - Recursive
 * n! = n * (n-1) * (n-2) * ... * 1
 */
function factorial(n) {
  // 1. Base Case
  if (n === 0 || n === 1) return 1;

  // 2. Recursive Step
  return n * factorial(n - 1);
}

/**
 * Fibonacci - Recursive (Brute Force)
 * O(2^n) - Very slow for large n
 */
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

---

Tail Recursion

Some languages optimize "Tail Recursion" (where the recursive call is the last thing in the function), making it as efficient as a loop. Note: JavaScript engines (except Safari) generally do not support this in practice yet.

Common Questions

• Explain the "Stack Overflow" error and how to prevent it.
• Convert this recursive function to an iterative one using a Stack.
• When is recursion better than iteration? (Answer: When navigating tree-like structures or using divide-and-conquer).