Engineering Fluency OS

Why This Matters

Some problems have a natural recursive structure: a folder contains files and other folders. A math expression contains numbers and other expressions. An HTML element contains text and other elements. Recursion is the technique of solving these problems by having a function call itself on smaller inputs.

Recursion is not just a clever trick — it's a fundamental problem-solving strategy. Tree traversal, divide-and-conquer algorithms, parsing nested structures, and many dynamic programming solutions are naturally recursive. Understanding the call stack is the key to understanding how recursion works.

Define Terms

Visual Model

main()

result=?

factorial(4)

n=4

factorial(3)

n=3

factorial(2)

n=2

factorial(1)→ 1

n=1

Call Stack

The full process at a glance. Click Start tour to walk through each step.

The call stack grows with each recursive call and unwinds as base cases return values back up.

Code Example

Code

// FACTORIAL: classic recursion example
function factorial(n) {
  // Base case: stop recursion
  if (n <= 1) return 1;
  // Recursive case: call self with smaller input
  return n * factorial(n - 1);
}
console.log(factorial(5));  // 120 (5*4*3*2*1)

// COUNTDOWN: simple recursive structure
function countdown(n) {
  if (n <= 0) {
    console.log("Go!");
    return;
  }
  console.log(n);
  countdown(n - 1);
}
countdown(3);  // 3, 2, 1, Go!

// SUM ARRAY: recursion on collections
function sumArray(arr) {
  if (arr.length === 0) return 0;  // base case
  return arr[0] + sumArray(arr.slice(1));  // recursive case
}
console.log(sumArray([1, 2, 3, 4]));  // 10

// FIBONACCI with memoization
function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(10));  // 55
console.log(fib(40));  // 102334155 (fast with memo!)

Interactive Experiment

Try these exercises:

Write a recursive function to reverse a string (hint: base case is empty string or 1 char).
What happens if you call factorial(-1)? What's missing?
Try computing fibonacci(40) without memoization vs with — time the difference.
Write a recursive function to flatten a nested array: [1, [2, [3, 4]], 5] → [1, 2, 3, 4, 5].

Quick Quiz

Coding Challenge

Recursive Power

Write a recursive function called `power` that takes a base and exponent and returns base^exponent. Don't use Math.pow or the ** operator. Handle exponent of 0 (returns 1).

Loading editor...

Real-World Usage

Recursion appears throughout software engineering:

File systems: Traversing directories (folders contain folders) is inherently recursive.
DOM traversal: Walking an HTML tree to find elements, apply styles, or extract text.
JSON parsing: JSON objects can nest other objects/arrays to arbitrary depth.
Merge sort: Recursively splits arrays in half, sorts each half, merges results.
React component trees: Components render child components that render child components.
Git: Commit history is a recursive linked structure (each commit points to its parent).

Recursion