
Recursion: Calling Yourself
Opening Russian Dolls. Without Base Case, it's Stack Overflow hell.

Opening Russian Dolls. Without Base Case, it's Stack Overflow hell.
Why does my server crash? OS's desperate struggle to manage limited memory. War against Fragmentation.

Two ways to escape a maze. Spread out wide (BFS) or dig deep (DFS)? Who finds the shortest path?

Fast by name. Partitioning around a Pivot. Why is it the standard library choice despite O(N²) worst case?

Establishing TCP connection is expensive. Reuse it for multiple requests.

As a junior developer, I was reviewing senior's code and got shocked. Saw a function calling itself, initially thought it was a bug:
function search(folder) {
search(folder.subfolders); // ← Calling itself?!
}
Me: "Isn't this an infinite loop? This function will never stop..."
Senior: "Not with Base Case. It's recursion. One of the most beautiful concepts in programming."
Me: "??? What's Base Case? And why beautiful?"
Senior pulled out a Matryoshka doll from his desk (yes, he actually had one on his desk). Opening the big doll revealed a smaller doll, which contained an even smaller doll, and so on. When the smallest doll appeared, senior said:
"This is recursion. Break big problem into smaller problem, smaller into even smaller, solve the tiniest problem, and the whole thing solves itself."That moment something clicked, but when I tried writing code, still felt lost. Boundary between infinite loop and recursion was fuzzy, didn't know what Call Stack was, couldn't understand why some problems require recursion.
First project: "Traverse entire folder structure to find files with specific extension." Project structure looked like:
project/
├─ src/
│ ├─ components/
│ │ ├─ Button.jsx
│ │ └─ Input.jsx
│ ├─ utils/
│ │ └─ helpers.js
│ └─ pages/
│ └─ Home.jsx
└─ public/
└─ assets/
└─ logo.png
Me: "Hmm... loop through folders with for loop... but if subfolder exists, loop again... but if it has another subfolder... huh?"
Senior: "Don't know how many nested folder levels exist. How many nested for loops will you write?"
Me: "......"
Senior: "This is exactly when recursion shines. Folder structure itself is recursive. Folder contains folders, which contain folders... Problem itself repeats same structure."
Started seriously studying recursion from that point.But initially felt brain-exploding. Following code execution, when function calls itself, brain freezes. Watching debugger, seeing Stack grow, kept thinking "when does this end?"
Points where I got stuck learning recursion:
Concept of function calling itself wasn't intuitive. Normal programming flows "top to bottom, sequentially", but suddenly "going back to itself" was hard to grasp.
Felt like calling itself naturally creates infinite loop, didn't understand how it stops. Before learning "Base Case" concept, thought every recursive function would end in Stack Overflow.
Called "termination condition", but didn't know exactly when and how it works. Especially criteria for "why this point is Base Case" wasn't clear.
Didn't know what Call Stack was, couldn't understand why poorly written recursive functions throw "Maximum call stack size exceeded" error. Took time to understand each recursive call stacks somewhere in memory.
Looking at factorial example, for loop much easier to understand and faster, couldn't understand why bother with recursion. Thought "recursion just for writing shorter code?"
Senior's Matryoshka analogy started making sense. Especially this explanation was the clincher:
Matryoshka Dolls (Russian Dolls):
Open big doll → small doll inside. Open that small doll → smaller doll. Keep opening → finally reach smallest doll that can't open anymore.
This smallest doll is Base Case.
Recursion same:
- Big problem → smaller problem
- Smaller → even smaller
- ...
- Solve smallest problem (Base Case)
- Answers assemble in reverse → whole problem solved
But truly understood when he gave "mirror facing mirror" analogy.
Mirror facing mirror creates infinitely repeating images. But actually, due to light reflection loss, becomes too dark to see at some point. That "too dark to see" moment is Base Case.
"Oh, not dividing problems, but problem itself is smaller version of itself!"After this realization, recursion became visible.
Recursive function must have these two:
function recursion(n) {
// 1. Base Case (termination condition)
if (n === 0) {
return "Done!"; // No more recursive calls
}
// 2. Recursive Case (recursive call)
// Make problem smaller and call itself again
return recursion(n - 1);
}
function infiniteRecursion(n) {
// ❌ No Base Case!
console.log(n);
return infiniteRecursion(n - 1); // Never stops
}
infiniteRecursion(5);
// 5
// 4
// 3
// 2
// 1
// 0
// -1
// -2
// ...
// 💥 Maximum call stack size exceeded
Why crash?
Every function call stacks on Call Stack. Without Base Case, Stack grows infinitely until hitting memory limit, causing Overflow.
function badRecursion(n) {
if (n === 0) return 0; // Base Case exists
return badRecursion(n); // ❌ Doesn't reduce n!
}
badRecursion(5);
// 💥 Maximum call stack size exceeded
Base Case exists, but n stays 5, never reaching Base Case. Without "Progress", Base Case useless.
5! = 5 × 4 × 3 × 2 × 1 = 120
function factorial(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result *= i;
}
return result;
}
console.log(factorial(5)); // 120
Code: Clear, fast, memory efficient
function factorial(n) {
// Base Case: smallest indivisible problem
if (n === 0 || n === 1) {
return 1;
}
// Recursive Case: big problem to small problem
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
Process:
factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120
Calling factorial(5), what exactly happens in memory?
┌──────────────────────┐
│ factorial(5) │ ← Currently executing
│ n = 5 │
│ return 5 * ??? │ (waiting for factorial(4))
└──────────────────────┘
[main]
Step 2: Call factorial(4)
┌──────────────────────┐
│ factorial(4) │ ← Currently executing
│ n = 4 │
│ return 4 * ??? │ (waiting for factorial(3))
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │ (waiting)
└──────────────────────┘
[main]
Step 3: Call factorial(3)
┌──────────────────────┐
│ factorial(3) │ ← Currently executing
│ n = 3 │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
Step 4: Call factorial(2)
┌──────────────────────┐
│ factorial(2) │ ← Currently executing
│ n = 2 │
│ return 2 * ??? │
├──────────────────────┤
│ factorial(3) │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
Step 5: Call factorial(1) (Base Case reached!)
┌──────────────────────┐
│ factorial(1) │ ← Currently executing
│ n = 1 │
│ return 1 │ ✅ Base Case!
├──────────────────────┤
│ factorial(2) │
│ return 2 * ??? │
├──────────────────────┤
│ factorial(3) │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
Now Stack unwinds in reverse, computing values:
Step 6: factorial(1) returns
┌──────────────────────┐
│ factorial(2) │ ← Now
│ n = 2 │
│ return 2 * 1 = 2 │ ✅
├──────────────────────┤
│ factorial(3) │
├──────────────────────┤
│ factorial(4) │
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 7: factorial(2) returns
┌──────────────────────┐
│ factorial(3) │ ← Now
│ n = 3 │
│ return 3 * 2 = 6 │ ✅
├──────────────────────┤
│ factorial(4) │
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 8: factorial(3) returns
┌──────────────────────┐
│ factorial(4) │ ← Now
│ n = 4 │
│ return 4 * 6 = 24 │ ✅
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 9: factorial(4) returns
┌──────────────────────┐
│ factorial(5) │ ← Now
│ n = 5 │
│ return 5 * 24 = 120 │ ✅
└──────────────────────┘
[main]
Step 10: Final return
[main] ← receives 120
After seeing this visualization, truly understood recursion "goes down stacking, comes up calculating".
Code I wrote at company. This shows recursion's true power.
project/
├─ src/
│ ├─ App.jsx
│ ├─ components/
│ │ ├─ Button.jsx
│ │ └─ Input.jsx
│ └─ utils/
│ └─ helpers.js
└─ README.md
Find all .jsx files. Problem: don't know folder depth beforehand.
function findFiles(folder, extension) {
const results = [];
// Check current folder's files
folder.files.forEach(file => {
if (file.endsWith(extension)) {
results.push(folder.path + '/' + file);
}
});
// 🔑 Recursion: traverse subfolders same way
folder.subfolders.forEach(subfolder => {
const subResults = findFiles(subfolder, extension); // Recursive call
results.push(...subResults);
});
return results;
}
const projectRoot = {
path: 'project',
files: ['README.md'],
subfolders: [
{
path: 'project/src',
files: ['App.jsx'],
subfolders: [
{
path: 'project/src/components',
files: ['Button.jsx', 'Input.jsx'],
subfolders: []
},
{
path: 'project/src/utils',
files: ['helpers.js'],
subfolders: []
}
]
}
]
};
const jsxFiles = findFiles(projectRoot, '.jsx');
console.log(jsxFiles);
// ['project/src/App.jsx', 'project/src/components/Button.jsx', 'project/src/components/Input.jsx']
With loop?
function findFilesIterative(rootFolder, extension) {
const results = [];
const stack = [rootFolder]; // Manually implement Stack
while (stack.length > 0) {
const folder = stack.pop();
folder.files.forEach(file => {
if (file.endsWith(extension)) {
results.push(folder.path + '/' + file);
}
});
// Add subfolders to Stack
folder.subfolders.forEach(subfolder => {
stack.push(subfolder);
});
}
return results;
}
Comparison:
The insight: Folder structure inherently recursive. Folders contain folders, containing folders. When problem itself recursive, recursion natural solution.
Saw Call Stack with factorial example, let's go deeper.
Every function call:
All this packed into Stack Frame unit, stacked on Call Stack.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(3);
Memory state:
Heap (dynamic memory)
┌─────────────────┐
│ (empty) │
└─────────────────┘
Call Stack
┌─────────────────┐
│ factorial(1) │ ← Top (currently executing)
│ n=1, return=1 │
├─────────────────┤
│ factorial(2) │
│ n=2, return=?? │ (waiting for factorial(1))
├─────────────────┤
│ factorial(3) │
│ n=3, return=?? │ (waiting for factorial(2))
├─────────────────┤
│ main() │
└─────────────────┘
Each Stack Frame small (few hundred bytes), but deep recursion stacks thousands/tens of thousands, consuming memory.
function badRecursion(n) {
console.log(n);
return badRecursion(n - 1); // No Base Case!
}
badRecursion(5);
Call Stack:
[badRecursion(-99999)]
[badRecursion(-99998)]
...
[badRecursion(0)]
[badRecursion(1)]
[badRecursion(2)]
[badRecursion(3)]
[badRecursion(4)]
[badRecursion(5)]
[main]
↓ Keeps stacking
💥 Maximum call stack size exceeded
let count = 0;
function testStack() {
count++;
testStack();
}
try {
testStack();
} catch (e) {
console.log(`Maximum: ${count} calls`);
}
// Node.js: ~12,000 calls
// Chrome: ~10,000 calls
// Firefox: ~50,000 calls
Varies by browser/environment, typically crashes around 10,000~50,000 calls.
Possible in Node.js:
node --stack-size=10000 script.js # Increase Stack to 10MB
But not fundamental solution. Need proper Base Case, convert to loop, or use Tail Call Optimization.
| Aspect | Recursion | Loop |
|---|---|---|
| Readability | Intuitive if problem recursive | Clear for simple iteration |
| Speed | Slower (function call overhead) | Faster |
| Memory | More (Call Stack) | Less |
| Debugging | Harder (complex Stack trace) | Easier |
| Code Length | Short and elegant | Can be verbose |
| Best for | Trees, graphs, divide & conquer | Simple iteration, counting |
| Avoid for | Simple iteration, large n | Tree traversal (code complex) |
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
console.time('fib(40)');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40)');
// fib(40): ~1.5 seconds 😱
Problem: Repeats same calculation massively
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2) ← Calculated
│ │ │ ├─ fib(1)
│ │ │ └─ fib(0)
│ │ └─ fib(1)
│ └─ fib(2) ← Calculated again (duplicate!)
│ ├─ fib(1)
│ └─ fib(0)
└─ fib(3) ← Calculated again (duplicate!)
├─ fib(2)
│ ├─ fib(1)
│ └─ fib(0)
└─ fib(1)
Computing fib(40) calls fib(2) a whopping 63,245,986 times!
Time complexity: O(2^n) - exponentially slow
function fib(n, memo = {}) {
// Return from cache if already calculated
if (n in memo) return memo[n];
// Base Case
if (n <= 1) return n;
// Calculate and cache
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
console.time('fib(40) with memo');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40) with memo');
// fib(40) with memo: ~0.5ms ⚡
3000x faster!
Time complexity: O(n)
function fib(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
console.time('fib(40) iterative');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40) iterative');
// fib(40) iterative: ~0.01ms ⚡⚡
Conclusion: For Fibonacci, iteration best. If using recursion, must use memoization.
10
/ \
5 15
/ \ / \
3 7 12 20
Want to print all nodes (DFS - Depth First Search).
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
function traverse(node) {
if (!node) return; // Base Case: reached null node
console.log(node.value); // Print current node
traverse(node.left); // Recursively traverse left subtree
traverse(node.right); // Recursively traverse right subtree
}
// Build tree
const root = new Node(10,
new Node(5,
new Node(3),
new Node(7)
),
new Node(15,
new Node(12),
new Node(20)
)
);
traverse(root);
// Output: 10, 5, 3, 7, 15, 12, 20 (Pre-order traversal)
Beautifully short: 6 lines
function traverseIterative(root) {
if (!root) return;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
console.log(node.value);
// Push right first (Stack is LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
}
traverseIterative(root);
// Output: 10, 5, 3, 7, 15, 12, 20
Code length: 14 lines, need manual Stack management
Understood: Recursive data structures like trees and graphs naturally solved with recursion. Forcing iterative solution feels like going against nature.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1); // ← Multiplication remains
}
After factorial(n - 1) returns, still need n * operation. Must maintain Stack Frame.
function factorial(n, acc = 1) {
if (n === 1) return acc;
return factorial(n - 1, n * acc); // ← Direct return (no additional work)
}
factorial(5, 1);
Process:
factorial(5, 1)
→ factorial(4, 5)
→ factorial(3, 20)
→ factorial(2, 60)
→ factorial(1, 120)
→ 120
Recursive call is last operation. Theoretically, compiler detecting this can reuse Stack like iteration for optimization.
JavaScript reality: Tail Call Optimization (TCO) included in ES6 spec, but most JS engines haven't implemented it (only Safari partial support).
// Return thunk version
function factorial(n, acc = 1) {
if (n === 1) return acc;
return () => factorial(n - 1, n * acc); // Return function
}
// Trampoline: if function keep executing, if value return
function trampoline(fn) {
while (typeof fn === 'function') {
fn = fn();
}
return fn;
}
console.log(trampoline(factorial(100000, 1)));
// Runs without Stack Overflow!
How it works:
factorial wraps next calculation in function (Thunk) and returnstrampoline executes these functions sequentially with looptrampoline stackedRealistically: If performance critical, just use loop. Trampoline fun for learning but has overhead in production.
| | |
||| | |
||||| | |
||||||| | |
||||||||| | |
───────── ───────── ─────────
A B C
Rules:
Key insight: To move n disks from A to C:
function hanoi(n, from, to, aux) {
if (n === 1) {
console.log(`Move disk 1 from ${from} to ${to}`);
return;
}
// Step 1: Move n-1 from 'from' to 'aux' (using 'to' as auxiliary)
hanoi(n - 1, from, aux, to);
// Step 2: Move largest disk from 'from' to 'to'
console.log(`Move disk ${n} from ${from} to ${to}`);
// Step 3: Move n-1 from 'aux' to 'to' (using 'from' as auxiliary)
hanoi(n - 1, aux, to, from);
}
hanoi(3, 'A', 'C', 'B');
Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Visualization (3 disks):
Initial state:
A B C
|||
|||||
───── ───── ─────
Move disk 1 from A to C:
A B C
|||
|||||
───── ───── ─────
Move disk 2 from A to B:
A B C
||||| |||
───── ───── ─────
Move disk 1 from C to B:
A B C
|||
|||||
───── ───── ─────
Move disk 3 from A to C:
A B C
||| |||||
|||||
───── ───── ─────
(continues...)
Solving this with loops? Nearly impossible. Recursion is only intuitive solution.
Time complexity: O(2^n) - slow but unavoidable (minimum moves is 2^n - 1)
function findElementById(node, id) {
// Base Case: found or no node
if (!node) return null;
if (node.id === id) return node;
// Recurse on all child nodes
for (let child of node.children) {
const found = findElementById(child, id);
if (found) return found;
}
return null;
}
const element = findElementById(document.body, 'my-button');
function deepClone(obj) {
// Base Case: primitive type
if (obj === null || typeof obj !== 'object') {
return obj;
}
// Array
if (Array.isArray(obj)) {
return obj.map(item => deepClone(item));
}
// Object
const cloned = {};
for (let key in obj) {
cloned[key] = deepClone(obj[key]); // Recursion
}
return cloned;
}
const original = {
name: 'John',
address: {
city: 'Seoul',
nested: {
deep: 'value'
}
},
hobbies: ['coding', ['nested', 'array']]
};
const copied = deepClone(original);
copied.address.city = 'Busan';
console.log(original.address.city); // 'Seoul' (unaffected)
function flatten(arr) {
const result = [];
for (let item of arr) {
if (Array.isArray(item)) {
result.push(...flatten(item)); // Recursion
} else {
result.push(item);
}
}
return result;
}
const nested = [1, [2, [3, [4, 5]], 6], 7];
console.log(flatten(nested));
// [1, 2, 3, 4, 5, 6, 7]
function permute(arr) {
const result = [];
// Base Case: empty or single element
if (arr.length <= 1) return [arr];
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
const perms = permute(remaining); // Recursion
for (let perm of perms) {
result.push([current, ...perm]);
}
}
return result;
}
console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Code I actually used at company:
const config = {
app: {
name: "MyApp",
settings: {
theme: "dark",
lang: "ko",
advanced: {
debug: true
}
}
},
db: {
host: "localhost",
port: 5432
}
};
// Find all leaf values
function findValues(obj, result = []) {
for (let key in obj) {
const value = obj[key];
if (typeof value === 'object' && value !== null) {
findValues(value, result); // Recursion
} else {
result.push(value);
}
}
return result;
}
console.log(findValues(config));
// ['MyApp', 'dark', 'ko', true, 'localhost', 5432]
// Find specific key (in nested object)
function findKey(obj, targetKey) {
if (targetKey in obj) {
return obj[targetKey];
}
for (let key in obj) {
if (typeof obj[key] === 'object' && obj[key] !== null) {
const found = findKey(obj[key], targetKey);
if (found !== undefined) return found;
}
}
return undefined;
}
console.log(findKey(config, 'debug')); // true
console.log(findKey(config, 'theme')); // 'dark'
// ❌ Wrong
function countdown(n) {
console.log(n);
countdown(n - 1); // Never stops
}
// ✅ Correct
function countdown(n) {
if (n < 0) return; // Base Case!
console.log(n);
countdown(n - 1);
}
// ❌ Wrong
function search(arr, target) {
if (arr[0] === target) return true;
return search(arr, target); // arr unchanged!
}
// ✅ Correct
function search(arr, target) {
if (arr.length === 0) return false;
if (arr[0] === target) return true;
return search(arr.slice(1), target); // Reduce array
}
// ❌ Dangerous
const result = [];
function traverse(node) {
if (!node) return;
result.push(node.value); // Mutate global variable
traverse(node.left);
traverse(node.right);
}
// ✅ Safe
function traverse(node, result = []) {
if (!node) return result;
result.push(node.value);
traverse(node.left, result);
traverse(node.right, result);
return result;
}
// ❌ Inefficient
function fib(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fib(n - 1) + fib(n - 2);
}
// Calling fib(-5)? Infinite loop!
// ✅ Defensive
function fib(n) {
if (n < 0) throw new Error('Negative input');
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// ❌ Unnecessary recursion
function sum(arr, index = 0) {
if (index === arr.length) return 0;
return arr[index] + sum(arr, index + 1);
}
// ✅ Just use loop
function sum(arr) {
let total = 0;
for (let num of arr) total += num;
return total;
}
// Or reduce
const sum = arr => arr.reduce((a, b) => a + b, 0);
function factorial(n, depth = 0) {
const indent = ' '.repeat(depth);
console.log(`${indent}factorial(${n}) called`);
if (n === 1) {
console.log(`${indent}→ Base Case! Return 1`);
return 1;
}
const result = n * factorial(n - 1, depth + 1);
console.log(`${indent}→ Return ${n} * ${result / n} = ${result}`);
return result;
}
factorial(5);
Output:
factorial(5) called
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
→ Base Case! Return 1
→ Return 2 * 1 = 2
→ Return 3 * 2 = 6
→ Return 4 * 6 = 24
→ Return 5 * 24 = 120
debugger; in browser consolefunction factorial(n) {
debugger; // Stops here
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5);
function safeFib(n, maxDepth = 100, depth = 0) {
if (depth > maxDepth) {
throw new Error(`Max recursion depth ${maxDepth} exceeded`);
}
if (n <= 1) return n;
return safeFib(n - 1, maxDepth, depth + 1) +
safeFib(n - 2, maxDepth, depth + 1);
}
When writing recursive function, verify these:
| Item | Description | Check |
|---|---|---|
| Base Case | Has case returning without recursive call? | ☐ |
| Progress | Does problem get smaller each call? Getting closer to Base Case? | ☐ |
| Correctness | Do both Base Case and Recursive Case return correct values? | ☐ |
| Termination | Will all inputs eventually reach Base Case? | ☐ |
| Edge Cases | Handled n=0, n=1, negative, null, empty array, etc? | ☐ |
| Performance | No repeated calculations? Need memoization? | ☐ |
| Stack Overflow | No possibility of excessive recursion depth? | ☐ |
| Alternative | Could loop be simpler or faster? | ☐ |
Recursion appropriate when:
Avoid recursion when:
Summary: Looking at problem, if thinking "this is small version of itself", use recursion. Tree is collection of subtrees, folder is collection of subfolders, JSON is collection of JSON. If problem resembles itself, solve with recursion.
Initially thought "recursion slow, complex, Stack Overflow risk, why bother?" Factorial faster with for loop, Fibonacci way more efficient with iteration.
Now completely different understanding:
"Recursion not for speed, but for expressiveness"Traversing folder structure, walking tree, parsing JSON, these problems inherently recursive. Solving with loops requires manually managing Stack, losing essence. Recursion is method of translating problem's essence directly to code.
Like Matryoshka dolls, big problem contains small problem, containing smaller problem. And solving tiniest problem magically solves whole.
The insight: