Recursion

1. Introduction

Recursion is a programming technique where a function calls itself to solve a problem. It works by breaking a complex problem down into smaller, identical sub-problems, eventually reaching a simple scenario that can be solved directly without further recursive calls.

2. Why It Matters

Recursion is particularly suited for solving problems that have a naturally nested or hierarchical structure, such as traversing nested DOM trees, processing JSON configurations, or implementing algorithms like quicksort and merge sort.

3. Real-World Analogy

Think of opening nested Russian Matryoshka Dolls:

• Recursive Step: You open a doll, only to find another identical, smaller doll inside. You repeat the process: open the new doll, locate the next smaller one inside.
• Base Case: You eventually open a doll and find a solid, tiny wooden doll that cannot be opened. The recursion stops here. You gather the contents and close the dolls back up one by one.

4. How It Works

A recursive function must contain two essential parts:
1. Base Case: The condition that stops the recursion. Without it, the function calls itself indefinitely, causing a stack overflow.
2. Recursive Step: The code block where the function calls itself with a modified, smaller argument, bringing it closer to the base case.

5. Call Stack Execution Flow

Every recursive call creates a new execution context and pushes it onto the Call Stack. The stack grows with each nested call. When the base case is finally hit, the stack resolves from the top down (Last-In, First-Out), passing return values back up through each caller context until the initial call completes.

6. Practical Example

This script demonstrates traversing a hierarchical DOM tree using recursion:

7. Common Mistakes

• Missing or incorrect base case: Causes the function to run indefinitely until the Call Stack runs out of memory, throwing a stack overflow error.
• Not modifying the recursive argument: Passing the same inputs repeatedly prevents the function from ever reaching the base case.

8. Quick Quiz

9. Scenario-Based Challenge

10. Debugging Exercise

function sumArray(arr) {
  // Objective: return sum of numbers inside arr
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr); // crashes!
}

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

11. Interview Questions

12. Production Considerations

• • Limit Deep Recursion: Because modern browser engines do not support Tail Call Optimization, avoid recursion for datasets with nesting depths greater than 10,000. Instead, refactor the code to use an iterative loop approach with an array-based stack to avoid stack overflows.