Engineering Fluency OS

Why This Matters

When you analyze merge sort, you discover that the time to sort n items equals twice the time to sort n/2 items plus n steps to merge: T(n) = 2T(n/2) + n. That equation is a recurrence relation — it defines a value in terms of smaller instances of itself. The Fibonacci sequence is the most famous recurrence: F(n) = F(n-1) + F(n-2). Every term is defined by the two terms before it.

Recurrence relations bridge recursive thinking and explicit formulas. When you find a closed-form solution, you can jump directly to F(100) without computing F(1) through F(99). This is the difference between O(n) iteration and O(1) direct computation. Understanding recurrences is essential for analyzing recursive algorithms, dynamic programming, and divide-and-conquer strategies.

Define Terms

Visual Model

Base CasesF(0) = 0, F(1) = 1

RecurrenceF(n) = F(n-1) + F(n-2)

Sequence0, 1, 1, 2, 3, 5, 8, 13, 21...

Recursion TreeExponential without memoization

Iterative SolutionO(n) time, O(1) space

Closed FormBinet formula: O(1)

Algorithm AnalysisT(n) = 2T(n/2) + n

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

Recurrence relations define sequences by their previous terms. The Fibonacci sequence is the classic example.

Code Example

Code

// Fibonacci: the classic recurrence relation
// F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

// Naive recursive (exponential time - do not use for large n)
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}
console.log("Recursive F(10):", fibRecursive(10)); // 55

// Iterative (O(n) time, O(1) space)
function fibIterative(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}
console.log("Iterative F(10):", fibIterative(10)); // 55
console.log("Iterative F(50):", fibIterative(50)); // 12586269025

// Compute first n terms of any recurrence
function computeRecurrence(baseCases, rule, n) {
  const seq = [...baseCases];
  for (let i = seq.length; i <= n; i++) {
    seq.push(rule(seq, i));
  }
  return seq;
}

// Fibonacci via generic recurrence
const fib = computeRecurrence([0, 1], (s, i) => s[i-1] + s[i-2], 10);
console.log("Fibonacci:", fib); // [0,1,1,2,3,5,8,13,21,34,55]

// Another recurrence: T(n) = 2*T(n-1) + 1, T(0) = 0
// (Tower of Hanoi moves)
const hanoi = computeRecurrence([0], (s, i) => 2 * s[i-1] + 1, 5);
console.log("Hanoi:", hanoi); // [0, 1, 3, 7, 15, 31]

// Closed form verification: Binet formula
const phi = (1 + Math.sqrt(5)) / 2;
const psi = (1 - Math.sqrt(5)) / 2;
function fibBinet(n) {
  return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / Math.sqrt(5));
}
console.log("Binet F(10):", fibBinet(10)); // 55

Interactive Experiment

Try these exercises:

Compute the first 20 Fibonacci numbers iteratively. When does the value exceed 1,000? 1,000,000?
Time the naive recursive function for F(30) vs F(40). How much slower is F(40)? Why?
Define the recurrence T(n) = T(n-1) + n with T(0) = 0. Compute the first 10 terms. What familiar formula does this produce?
The Tribonacci sequence uses T(n) = T(n-1) + T(n-2) + T(n-3). Compute its first 15 terms starting from T(0)=0, T(1)=0, T(2)=1.
Verify that the Binet formula matches iterative Fibonacci for n = 0 through 30. At what point do floating-point errors appear?

Quick Quiz

Coding Challenge

Compute Recurrence Terms

Write a function called `solveRecurrence` that takes three arguments: `baseCases` (an array of initial values), `n` (the term number to compute), and `numPrevTerms` (how many previous terms each new term depends on). Each new term is the sum of the previous `numPrevTerms` terms. Return the value of the n-th term (0-indexed). For example, Fibonacci has baseCases=[0,1], numPrevTerms=2. Tribonacci has baseCases=[0,0,1], numPrevTerms=3.

Loading editor...

Real-World Usage

Recurrence relations appear throughout computer science and engineering:

Algorithm analysis: The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n), giving time complexities for merge sort (O(n log n)), binary search (O(log n)), and Karatsuba multiplication.
Dynamic programming: Every DP solution is based on a recurrence. The knapsack problem, shortest paths, and edit distance all use recurrences to break problems into subproblems.
Financial modeling: Compound interest follows a recurrence: A(n) = A(n-1) * (1 + r). Loan amortization and investment growth use similar recurrences.
Signal processing: Infinite impulse response (IIR) filters are defined by recurrences that relate output samples to previous outputs and inputs.
Population biology: The Fibonacci sequence originally modeled rabbit population growth. Ecological models often use recurrence relations.

Recurrence Relations