Thinking Recursively in JavaScript

Thinking Recursively in JavaScript

Recursion is when a function calls itself. It is essential for tree traversal, divide-and-conquer, and problems with self-similar structure.

The Two Parts

1. Base case: when to stop (the simplest case).
2. Recursive case: call the function with a smaller input.

Example: Factorial

function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case
}

Example: Fibonacci

function fib(n) {
  if (n < 2) return n; // base case
  return fib(n - 1) + fib(n - 2); // recursive case
}

Example: Tree Traversal

function traverse(node) {
  console.log(node.value);
  if (node.children) node.children.forEach(traverse);
}

How to Think Recursively

1. Identify the base case (when does it stop?).
2. Identify the recursive case (how to reduce the problem?).
3. Trust the recursion (assume the smaller call works).
4. Combine the result.

The Takeaway

Recursion: base case (stop) + recursive case (smaller input). Think: what is the simplest case? How do I reduce the problem? Trust the recursion. Use for: trees, divide-and-conquer, self-similar problems.