Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It typically consists of:

Base Case: Stops recursion.
Recursive Case: Calls itself with simpler input.

JavaScript manages recursive calls using an execution context stack:

Each call creates a new execution context (a record of variables, scope, and control flow).
Contexts are pushed onto the call stack, paused, and resumed after subcalls complete.

Example: Recursive power function:

function pow(x, n) {
  return (n === 1) ? x : x * pow(x, n - 1);
}

2. 🧠 Fill Gaps in Understanding

Stack Behavior Deep Dive

Each function call adds a frame to the stack:

pow(2, 3)
  → pow(2, 2)
    → pow(2, 1)
      → returns 2
    ← returns 4
  ← returns 8

The stack unwinds last-in-first-out (LIFO). Each frame has:

Parameters (x, n)
Local variables
Instruction pointer (line of code)
Return address

Why Use Recursion?

Use recursion when:

The problem is naturally hierarchical (tree, nested structures).
You want cleaner, more elegant code.
The problem divides into identical smaller subproblems.

⚠️ Stack size limit: Around 10,000 calls in most JS engines. Going deeper can cause RangeError: Maximum call stack size exceeded.

3. 💪 Challenge Me Deeply

10 Advanced Recursive Coding Problems

Factorial (Classic Base Case)

jfunction factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Sum of Nested Array

function deepSum(arr) {
  return arr.reduce((sum, el) =>
    sum + (Array.isArray(el) ? deepSum(el) : el), 0);
}

Fibonacci (Exponential Recursion)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Optimized Fibonacci (Memoization)

function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

Flatten Deep Object

function flattenObject(obj, prefix = '', res = {}) {
  for (let key in obj) {
    const newKey = prefix ? `${prefix}.${key}` : key;
    if (typeof obj[key] === 'object' && obj[key] !== null && !Array.isArray(obj[key])) {
      flattenObject(obj[key], newKey, res);
    } else {
      res[newKey] = obj[key];
    }
  }
  return res;
}

Reverse a String Recursively

function reverse(str) {
  if (str === '') return '';
  return reverse(str.slice(1)) + str[0];
}

Recursive Directory Size Sum

function getDirectorySize(dir) {
  if (Array.isArray(dir)) {
    return dir.reduce((sum, file) => sum + file.size, 0);
  }
  let size = 0;
  for (const sub of Object.values(dir)) {
    size += getDirectorySize(sub);
  }
  return size;
}

Tree Depth

function maxDepth(tree) {
  if (!tree || !tree.children) return 1;
  return 1 + Math.max(...tree.children.map(maxDepth));
}

All Subsets of Array

function subsets(arr) {
  if (arr.length === 0) return [[]];
  const rest = subsets(arr.slice(1));
  return [...rest, ...rest.map(sub => [arr[0], ...sub])];
}

Binary Search (Recursive)

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  return binarySearch(arr, target, mid + 1, right);
}

4. 🧪 Interview-Ready Questions

Conceptual

What is recursion? When would you choose it over iteration?
What is a base case in recursion and why is it crucial?
What happens if a recursive function has no base case?
Explain the call stack and how it relates to recursion.
What are tail calls, and why are they important?
How can recursion lead to memory issues?

Coding Questions

Implement a recursive function to flatten an arbitrarily nested array.
Write a recursive deep clone function.
Traverse a binary tree and sum all node values.
Parse a nested comment thread structure and count total comments.

5. 🧑‍💻 Real-World Usage Examples

DOM Traversal: DOM tree is naturally recursive.
Component Trees in React: Rendering deeply nested children.
Directory Traversal: Recursively walking filesystem (e.g., in Node.js).
Data Validation: Recursively validating deeply nested schemas (e.g., JSON).
Parsing: JSON, XML, or custom DSLs often require recursive descent parsing.

6. 🎯 Memory Aids

Mnemonics

"BASE before RECURSE" — Always define your base case first.
"Divide and Call" — Break the problem and call the function on the parts.

Analogy

Think of recursion as solving a Matryoshka doll problem. Open the big one to reveal a smaller one, repeat until you reach the smallest doll (base case), then start putting them back together (returning results).

7. 🎨 Fun Project: Recursive File Explorer (with Mock Data)

Build:

A terminal-like tree display for directories using recursion.

const fsMock = {
  root: {
    docs: {
      'resume.pdf': null,
      'cover-letter.docx': null,
    },
    photos: {
      vacation: {
        'beach.png': null,
        'hotel.jpg': null
      }
    }
  }
};

function printTree(obj, indent = '') {
  for (let key in obj) {
    console.log(indent + key);
    if (obj[key]) {
      printTree(obj[key], indent + '  ');
    }
  }
}

printTree(fsMock.root);

🧪 Challenge: Add file sizes, compute total size, or allow user input for navigation.

8. 🛠️ Pro Tips

Avoid unnecessary recursion in performance-sensitive code (e.g., parsing huge arrays).
Consider memoization to optimize overlapping recursive calls (e.g., Fibonacci).
Use tail recursion if supported by the engine.
Monitor call stack depth to avoid stack overflow.

Lesson 47: Mastering JavaScript Recursion and stack with challenges!