🔄 Recursion & Backtracking — JavaScript Complete Topic Index
Parent: DSA Master Index
📦 Subtopics
| # | Subtopic | File | Key Concepts |
|---|
| 1 | Recursion Basics | 01-basics/ | Call stack, base case, recursive case, stack overflow |
| 2 | Recursion Patterns | 02-patterns/ | Tree recursion, D&C, permutations, subsets |
| 3 | Backtracking | 03-backtracking/ | N-Queens, maze, Sudoku, combination sum |
| 4 | Interview Questions | 04-interview-questions/ | Top 25 questions with full solutions |
🧠 Recursion — Big Picture
Recursion
├── Base Case → Stops infinite recursion
├── Recursive Case → Breaks problem into smaller sub-problems
├── Call Stack → Each call gets its own frame
├── Direct Recursion → f() calls f()
├── Indirect Recursion → f() calls g(), g() calls f()
└── Backtracking → Recursion + Undo (explore, choose, unchoose)
⏱️ Complexity Cheat Sheet
| Problem | Time | Space (call stack) |
|---|
| Factorial n | O(n) | O(n) |
| Fibonacci naive | O(2ⁿ) | O(n) |
| Fibonacci memoized | O(n) | O(n) |
| Binary Search | O(log n) | O(log n) |
| Merge Sort | O(n log n) | O(n) |
| Generate all subsets | O(2ⁿ) | O(n) |
| Generate permutations | O(n!) | O(n) |
| N-Queens | O(n!) | O(n) |
| Sudoku Solver | O(9^81) worst | O(81) |
🎯 Backtracking Template (JavaScript)
function backtrack(result, current, ...params) {
// 1. Base case — found a complete solution
if (isComplete(current)) {
result.push([...current]); // save a copy
return;
}
// 2. Try every possible choice
for (const choice of getChoices(params)) {
if (!isValid(choice)) continue; // prune
// 3. Choose
current.push(choice);
// 4. Explore
backtrack(result, current, /* updated params */);
// 5. Un-choose (backtrack)
current.pop();
}
}
🔑 JS-Specific Notes
| Concept | PHP | JavaScript |
|---|
| Memoization | $memo = [] passed by ref | const memo = new Map() or closure |
| Pass by ref | &$arr | Objects/arrays are reference-like; use spread [...arr] to copy |
| Default param | ?int $right = null | right = nums.length - 1 |
| Array copy | $result[] = $current | result.push([...current]) |