When Recursion Goes Wrong

1
2
3
4
5
6
7

function countdown(n: number): void {
    console.log(n);
    countdown(n - 1);  // No base case - this WILL overflow
}
 
// Calling with any positive number
countdown(100000);  // Stack overflow guaranteed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Estimate stack usage for a recursive function
 
function estimateStackUsage(
    bytesPerFrame: number,
    maxRecursionDepth: number
): string {
    const totalBytes = bytesPerFrame * maxRecursionDepth;
    const totalKB = totalBytes / 1024;
    const totalMB = totalKB / 1024;
    
    return `
    Stack Frame Size: ${bytesPerFrame} bytes
    Recursion Depth:  ${maxRecursionDepth.toLocaleString()} calls
    ─────────────────────────────────
    Total Stack Usage: ${totalBytes.toLocaleString()} bytes
                       ${totalKB.toFixed(2)} KB
                       ${totalMB.toFixed(2)} MB
    `;
}
 
// Example: Simple function with 2 local numbers
console.log(estimateStackUsage(64, 10000));
// Total: ~640 KB - Safe on most systems
 
// Example: Function with array buffer
console.log(estimateStackUsage(4096, 10000));
// Total: ~40 MB - Will definitely overflow!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// ITERATIVE: Loop depth is always 1
// Stack usage: O(1) - constant regardless of n
function sumIterative(n: number): number {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}
 
// RECURSIVE: Call depth equals n
// Stack usage: O(n) - grows with input
function sumRecursive(n: number): number {
    if (n <= 0) return 0;
    return n + sumRecursive(n - 1);  // n stack frames needed
}
 
// Safe: sumIterative(1_000_000) - works fine
// Dangerous: sumRecursive(1_000_000) - STACK OVERFLOW

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Naive Fibonacci - despite exponential time,
// stack depth is only O(n) because branches complete
function fib(n: number): number {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
    // Max stack depth at any moment: n frames
    // (because we go deep left first, then return)
}
 
// BUT: This similar-looking function is worse
function generateAllBinaryStrings(n: number, current: string = ""): string[] {
    if (n === 0) return [current];
    
    // We create arrays that grow exponentially
    // AND they exist simultaneously on the stack
    const withZero = generateAllBinaryStrings(n - 1, current + "0");
    const withOne = generateAllBinaryStrings(n - 1, current + "1");
    
    return [...withZero, ...withOne];  // Massive memory in each frame
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

interface TreeNode {
    value: number;
    children: TreeNode[];
}
 
function sumTree(node: TreeNode | null): number {
    if (!node) return 0;
    
    let total = node.value;
    for (const child of node.children) {
        total += sumTree(child);  // Recursion depth = tree height
    }
    return total;
}
 
// For a balanced tree with 1 million nodes: depth ~20 (safe)
// For a degenerate linked-list tree with 1 million nodes: 
//   depth = 1,000,000 (STACK OVERFLOW)
 
// In production, you often can't control tree shape!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Strategy 1: Depth counter for diagnosis
function processTreeWithTracking(
    node: TreeNode | null, 
    depth: number = 0,
    maxSeenDepth: { value: number } = { value: 0 }
): number {
    // Track maximum depth seen
    maxSeenDepth.value = Math.max(maxSeenDepth.value, depth);
    
    // Log at significant intervals
    if (depth > 0 && depth % 1000 === 0) {
        console.log(`Recursion depth reached: ${depth}`);
    }
    
    // Fail fast with useful info
    if (depth > 50000) {
        throw new Error(
            `Recursion depth exceeded 50,000 at node value: ${node?.value}. \n` +
            `Consider using iterative approach or checking for cycles.`
        );
    }
    
    if (!node) return 0;
    
    let total = node.value;
    for (const child of node.children) {
        total += processTreeWithTracking(child, depth + 1, maxSeenDepth);
    }
    return total;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Strategy 2: Cycle detection with Set
function processGraphSafely<T extends { id: string; neighbors: T[] }>(
    node: T,
    visited: Set<string> = new Set()
): void {
    // Check for cycle before recursing
    if (visited.has(node.id)) {
        console.warn(`Cycle detected: node ${node.id} already visited`);
        return;
    }
    
    visited.add(node.id);
    
    // Process node...
    console.log(`Processing: ${node.id}`);
    
    // Recurse on neighbors
    for (const neighbor of node.neighbors) {
        processGraphSafely(neighbor, visited);
    }
}
 
// This prevents infinite recursion from cycles in the data structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// BEFORE: Recursive tree traversal (vulnerable)
function sumTreeRecursive(node: TreeNode | null): number {
    if (!node) return 0;
    let sum = node.value;
    for (const child of node.children) {
        sum += sumTreeRecursive(child);
    }
    return sum;
}
 
// AFTER: Iterative with explicit stack (safe)
function sumTreeIterative(root: TreeNode | null): number {
    if (!root) return 0;
    
    let sum = 0;
    const stack: TreeNode[] = [root];
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        sum += node.value;
        
        // Push children onto stack (reverse order for same traversal order)
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return sum;
}
 
// The iterative version uses heap memory for the stack array,
// which can grow to gigabytes instead of the ~8MB call stack limit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// The trampoline pattern converts deep recursion into iteration
// by returning a thunk (function to call) instead of calling directly
 
type Thunk<T> = () => T | Thunk<T>;
 
function trampoline<T>(fn: Thunk<T>): T {
    let result = fn();
    while (typeof result === 'function') {
        result = result();
    }
    return result;
}
 
// Trampolined factorial - never overflows
function factorialTrampoline(n: number, acc: number = 1): number | Thunk<number> {
    if (n <= 1) return acc;
    
    // Return a thunk instead of recursing
    return () => factorialTrampoline(n - 1, n * acc);
}
 
// Usage
const result = trampoline(() => factorialTrampoline(100000));
// Works even with n = 100,000 (though result overflows to Infinity)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class RecursionDepthExceededError extends Error {
    constructor(
        message: string,
        public readonly depth: number,
        public readonly limit: number
    ) {
        super(message);
        this.name = 'RecursionDepthExceededError';
    }
}
 
function processWithLimit<T>(
    node: TreeNode | null,
    processor: (node: TreeNode) => T,
    depth: number = 0,
    maxDepth: number = 10000
): void {
    if (depth > maxDepth) {
        throw new RecursionDepthExceededError(
            `Recursion depth ${depth} exceeded limit of ${maxDepth}. ` +
            `Data may be too deeply nested or contain cycles.`,
            depth,
            maxDepth
        );
    }
    
    if (!node) return;
    
    processor(node);
    
    for (const child of node.children) {
        processWithLimit(child, processor, depth + 1, maxDepth);
    }
}
 
// Caller can catch and handle gracefully
try {
    processWithLimit(suspiciousTree, (n) => console.log(n.value));
} catch (e) {
    if (e instanceof RecursionDepthExceededError) {
        console.error(`Tree too deep: limit was ${e.limit}`);
        // Fall back to iterative approach or reject the input
    }
}