Recursion is not a different algorithm from a loop-plus-stack. Each call pushes a frame: the arguments, the local variables, and the address to resume when the callee returns. When the callee returns, that frame pops. DFS on a tree, backtracking, and divide-and-conquer are this motion.
The difference is who owns the stack. The language owns the call stack. You own an explicit vector / array used as a stack. Same LIFO. Different failure modes.
function walk(i, a) {
if (i === a.length) return 0; // base: empty suffix
return a[i] + walk(i + 1, a);
}Read the base case out loud: the suffix starting at `i` is empty when `i === n`. That is an off-by-one waiting to happen. i > n is one step too late (a[n] is already undefined). i === n - 1 as a base returns without adding the last element. Name the range the same way you name an array slice: this function owns a[i..n) — half-open, last included index is n - 1.
function dfsIter(start, adj) {
const stack = [start];
const seen = new Set([start]);
while (stack.length) {
const u = stack.pop();
for (const v of adj[u]) {
if (seen.has(v)) continue;
seen.add(v);
stack.push(v);
}
}
}The explicit stack lives on the heap. A vector of 2·10⁵ ints is a rounding error against a 256 MB limit. The call stack is not that budget. When a solution is 'DFS on the implicit graph of size n' and n is 2·10⁵, write the iterative version, or recurse on a tree after you have confirmed the height is O(log n) (balanced) — not after you have confirmed the *graph* has n nodes.
Matching brackets is the same LIFO. Valid Parentheses in the arena is an explicit stack: push openers, pop on a closer. A recursive descent parser would use the call stack for the same nesting. If the string length is 10⁵, you still want the array.
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // TLE for n ≳ 40
}Checks 0/3