Algorithms in Node: Recursion, Trees, and Graph Traversal
Recursion, its real costs, and how to model and walk trees and graphs with plain Node.
Map/Set, and fs/promises from the intermediate course. By the end of this lesson you will be able to:
- write a recursive function with a correct base case and reason about its call stack;
- name the trade-offs of recursion and use memoization where it actually helps;
- model a tree and a graph in Node, and walk a directory tree;
- resolve dependencies with a topological order and detect cycles;
- implement and choose between breadth-first (BFS) and depth-first (DFS) search.
1. Recursion: base case and recursive case
A recursive function calls itself on a smaller version of the same problem. Every correct recursion has exactly two parts: a base case that returns an answer directly without recursing, and a recursive case that does a little work and then calls itself on something closer to the base.
function factorial(n) {
if (n <= 1) return 1; // base case: stop recursing
return n * factorial(n - 1); // recursive case: shrink toward the base
}
console.log(factorial(5)); // 120Read it as a contract: factorial(5) trusts factorial(4) to be correct, multiplies by 5, and returns. The base case (n <= 1) is what stops the descent. Remove it and the function never terminates.
Analogy. Recursion is a set of Russian nesting dolls. To count the dolls you open the outer one (a little work), then ask the same question of the doll inside (the recursive call). The smallest solid doll that cannot be opened is the base case — without it you would keep opening forever.
Recursion shines when the data itself is nested to an unknown depth — folders inside folders, or a comment thread with replies to replies. A flat for loop cannot easily express "and repeat this for each child, however deep it goes"; recursion can.