🔄 Recursion & Backtracking — PHP 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
function backtrack(array &$result, array &$current, ...$params): void
{
// 1. Base case — found a complete solution
if (isSolution($current)) {
$result[] = $current;
return;
}
// 2. Try every possible choice
foreach (choices($params) as $choice) {
// 3. Choose
$current[] = $choice;
// 4. Explore
backtrack($result, $current, /* updated params */);
// 5. Un-choose (backtrack)
array_pop($current);
}
}
🔑 When to Use Recursion vs Iteration
| Situation | Use Recursion | Use Iteration |
|---|
| Tree/Graph traversal | ✅ Natural | Possible with stack |
| Divide & Conquer | ✅ Cleaner | Possible but complex |
| Backtracking | ✅ Required | Very hard |
| Simple loops | ❌ Overhead | ✅ Faster |
| Deep recursion (n>10000) | ❌ Stack overflow risk | ✅ Safe |