The answer is made of earlier answers

A staircase has $n$ steps. Each move climbs either one step or two. How many different move sequences reach the top?

Do not list every route to step five. Classify routes by their final move. Every route ending in a one-step move comes from a route to step four. Every route ending in a two-step move comes from a route to step three. The cases are disjoint and complete.

In words: the present count is the sum of the previous two counts. Only now compress the sentence:

$$W(n) = W(n-1) + W(n-2).$$

The equation is incomplete until descent has somewhere to stop. There is one way to climb zero remaining steps—do nothing—and one way to climb one step:

$$W(0)=1,\qquad W(1)=1.$$

These are the base cases. They are not awkward exceptions. They are the smallest complete truths from which every larger answer is forced.

Starting from the base cases gives $1,1,2,3,5,8,\ldots$, the sequence commonly called the Fibonacci sequence.

Unfold the equation and the work appears

Translate the recurrence literally into a function. To compute $W(5)$, it computes $W(4)$ and $W(3)$. But $W(4)$ also computes $W(3)$. The same question is answered twice; deeper questions are repeated more often.

Without memory, the call tree has roughly as many leaves as the answer itself, so its size grows exponentially. With memoization, only $W(0)$ through $W(n)$ are distinct. The work becomes linear in $n$. An algebraic equation did not change; the representation of repeated questions did.

This is Chapter 7's identity question returning in algorithmic clothing. When two subcalls ask the same question, treating them as the same node is the difference between a tree of repeated work and a shared graph.

Some recurrences spread; others stack

Merge sort divides $n$ items into two halves, sorts both halves, then merges them in work proportional to $n$. Its cost obeys

$$T(n)=2T(n/2)+cn.$$

Read it aloud: two half-sized problems, plus one linear merge. Unfold one level. There are two merges of size $n/2$, whose total work is still proportional to $n$. The next level has four merges of size $n/4$; again the total is proportional to $n$.

The input can be halved only about $\log_2 n$ times before pieces reach size one. Each level costs $cn$, and there are $\log_2 n$ levels:

$$T(n)=\Theta(n\log_2 n).$$

A field guide, not a fortune teller

Many divide-and-conquer recurrences have the shape

$$T(n)=aT(n/b)+f(n).$$

There are $a$ subproblems, each $1/b$ the original size, plus local work $f(n)$. The Master theorem compares the work accumulating in the recursive leaves with the local work done while combining:

• If leaf growth dominates, the leaves determine the answer.
• If every level contributes the same order of work, multiply one level by the number of levels.
• If combine work dominates strongly enough, the root-side work determines the answer.

The theorem is a classifier for a particular family, not an oracle for every recurrence. Unequal splits, unusual additive terms, or missing regularity conditions require another method: expansion, substitution, recursion trees, or a more general theorem.

Eventual victory and today's crossover

Big O is often spoken as if it were a stopwatch. It is not. $O(g(n))$ gives an eventual upper growth bound; $\Omega(g(n))$ gives an eventual lower bound; $\Theta(g(n))$ gives both. Constant factors and smaller terms are deliberately hidden.

Compare two measured costs:

$$A(n)=100n,\qquad B(n)=n^2.$$

The quadratic algorithm $B$ is faster for $n<100$. At $n=100$ they meet. Beyond that, the linear algorithm wins by a growing margin.

This is why mature libraries sometimes keep two implementations and switch at a measured threshold. The asymptotically superior algorithm determines the large-input branch. The simpler low-constant algorithm earns the small-input exception.

What the equation cannot know for you

A recurrence is only as honest as its cost model. If “merge costs $cn$” ignores cache misses, allocation, parallel scheduling, or adversarial input, the solution describes the simplified machine—not production.

Asymptotics also does not license dropping constants at the scale users actually inhabit. Nor does a benchmark establish the growth rate: a short range can make $n\log n$ and $n^2$ look nearly interchangeable.

Use both views. Prove the shape of growth from the algorithm; measure the constants and crossover on the real platform.

Lessons

• A recurrence and its recursive function describe the same dependency.
• Base cases are the truths that make recursive descent terminate.
• Unfolding a recurrence exposes repeated subproblems and total work.
• Memoization turns identical subcalls into one shared answer.
• A divide-and-conquer tree can be analyzed level by level.
• Asymptotic growth predicts eventual dominance; constants locate the real crossover.
• The Master theorem covers a useful recurrence family, not every recursive program.

Practice

The call tree was never really a tree

Memoization changed the staircase computation by merging every repeated question into one node. Some nodes fed several later answers. The result was not a tree but a directed graph of dependencies.

If one remembered answer changes, exactly which later answers become stale—and what structural defect would make a valid evaluation order impossible?

References

1. Abel, Chapman & Demaine. “Lecture 07: Recurrences.” MIT OpenCourseWare, 2024. — modeling program costs with recurrences and solving common families
2. Abel, Chapman & Demaine. “Lecture 06: Asymptotics.” MIT OpenCourseWare, 2024. — formal O, Omega, and Theta definitions and growth comparisons
3. Lehman, Leighton & Meyer. “Mathematics for Computer Science, Chapter 10: Recurrences.” MIT OpenCourseWare, 2010. — recurrence trees, merge sort, and the Master theorem's scope
4. Leonardo of Pisa; translated by Laurence Sigler. “Fibonacci's Liber Abaci.” Springer, 2002 translation of 1202 work. — primary work containing Leonardo's rabbit recurrence
5. O'Connor & Robertson. “Leonardo Pisano Fibonacci.” MacTutor History of Mathematics. — institutional biography and context for Liber Abaci
6. O'Connor & Robertson. “Hemachandra.” MacTutor History of Mathematics. — evidence that related Indian recurrence work predates Liber Abaci