Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It's the foundation for many advanced algorithms like DFS, Merge Sort, and Dynamic Programming.

Think of a Russian Nesting Doll:

1. To open the biggest doll, you have to open the one inside it.
2. To open that one, you open the next one.
3. Eventually, you reach the smallest doll that cannot be opened.
4. You then close them all back up.

The "smallest doll" is what we call the Base Case.

---

The Three Laws of Recursion

1. The Base Case: A condition where the recursion stops. Without this, you'll get a "Stack Overflow" error.
2. The Recursive Step: The function calling itself with a "smaller" or "closer to base case" input.
3. State Management: Knowing what data to pass down and what to return back up.

How the Call Stack Works

When a recursive call is made, the current function's execution is paused, and its state is saved on the "Stack". Only when the child function returns can the parent resume.

---

javascript Standard
/**
 * Classic Example: Factorial (n!)
 * n! = n * (n-1) * (n-2)... * 1
 */
function factorial(n) {
  // 1. Base Case: smallest possible 'n'
  if (n <= 1) return 1;

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

/**
 * Visualizing the Call Stack for factorial(3):
 * -> factorial(3) returns 3 * factorial(2)
 *    -> factorial(2) returns 2 * factorial(1)
 *       -> factorial(1) returns 1 (Base Case)
 *    <- factorial(2) resumes, returns 2 * 1 = 2
 * <- factorial(3) resumes, returns 3 * 2 = 6
 */

/**
 * Finding the Sum of an Array recursively
 */
function recursiveSum(arr, index = 0) {
  // Base case: we've looked at all elements
  if (index === arr.length) return 0;

  // Recursive step: current element + sum of the rest
  return arr[index] + recursiveSum(arr, index + 1);
}

---

Recursion vs. Iteration

• Recursion: Easier to read and write for tree-like or complex structures (e.g., File systems).
• Iteration: More memory-efficient as it doesn't build up a call stack.

Pro-Tip

If your recursive solution is too slow due to repeated work (like in Fibonacci), use Memoization (storing results in a Map) to speed it up. This is the first step toward Dynamic Programming!