Case Study: Recurrence Forensics — Diagnosing Three Slow Recursive Functions

"It is not enough to know that a program is slow; you must know why, and by how much, and what it would take to fix it."

Executive Summary

A service is timing out. The on-call engineer has narrowed it to three recursive helper functions, all of which "look fine" and pass their unit tests, yet one of them makes the request latency explode as the input grows. In this analysis-heavy case study you will play that engineer: for each function you will read the recurrence directly off the code (§18.6), solve that recurrence by hand to a closed form or growth rate (§18.4–§18.5), and rank the three functions by how their cost scales. You will not rewrite anything until the final phase — the whole point is that the recurrence tells you which one is the problem before you touch a profiler. This is §18.6's "code → recurrence → growth rate" reflex used exactly as it is used in real performance work.

Skills applied

• Extracting a time recurrence $T(n)$ from recursive code (count the calls; count the per-call work).
• Solving a first-order nonhomogeneous recurrence by unrolling and by the particular-solution method (§18.5).
• Recognizing the Fibonacci-shaped recurrence and reading off exponential growth (§18.2, §18.6).
• Distinguishing the recurrence for a function's value from the recurrence for its running time.
• Translating closed-form growth into an engineering decision.

Background

The scenario

The team maintains a small analytics library. Three recursive helpers are under suspicion. Here they are, lightly cleaned up, each with the one unit test it passes in the pull request. (This is a constructed teaching scenario — Tier 3 — but the functions are entirely ordinary.)

# Helper 1: sum a list by peeling off the head.
def list_sum(xs):
    if not xs:                       # base case
        return 0
    return xs[0] + list_sum(xs[1:])  # one call on n-1 elements

# Helper 2: count "score paths" — the number of ways to reach score n
# taking steps worth 1 or 2 points (an ordered count).
def score_paths(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return score_paths(n - 1) + score_paths(n - 2)   # two calls

# Helper 3: a "depth report" that scans the input once, then recurses on half.
def depth_report(n):
    if n <= 1:
        return 0
    work = sum(1 for _ in range(n))      # a linear scan: ~n units of work
    return work + depth_report(n // 2)   # one call on n/2

print(list_sum([3, 1, 4, 1, 5]))   # 14
print(score_paths(5))              # 8
print(depth_report(8))             # 8 + 4 + 2 = 14
# Expected output:
# 14
# 8
# 14

All three are correct. The question is not correctness — it is cost. The service handles inputs in the thousands, and one of these three is the culprit.

💡 Intuition: Before any algebra, eyeball the shape of each function the way §18.6 trains you to. Helper 1 makes one call on a slightly smaller input. Helper 2 makes two calls on nearly-full inputs. Helper 3 makes one call but does a linear scan first, and shrinks by a factor. Those three shapes have three completely different recurrences — and three completely different growth rates. We are about to make that precise.

Why this matters

"It passed the tests" tells you the function returns the right answer; it tells you nothing about how the running time scales. Theme two of this book is exactly this gap: tests check behavior on the cases you tried, and the cases you tried in a unit test are small. The recurrence, solved, settles the behavior for all input sizes — including the production-sized ones you never tested. That is why the recurrence, not the profiler, is the first tool to reach for.

Phase 1: Helper 1 — one call, constant work

Let $T_1(n)$ be the number of basic operations list_sum performs on a list of $n$ elements (counting the arithmetic and the call overhead, not the hidden cost of slicing — see the Discussion). The base case is a constant amount of work, $T_1(0) = d$ for some constant $d$. Each non-base call does a constant amount of work (one addition, one index) and makes one recursive call on $n-1$ elements:

$$T_1(n) = T_1(n-1) + c, \qquad T_1(0) = d.$$

This is a first-order nonhomogeneous recurrence with a constant forcing term — exactly the first row of the §18.6 table. Solve it two ways to build confidence.

By unrolling. Substitute the recurrence into itself: $$T_1(n) = T_1(n-1) + c = T_1(n-2) + 2c = T_1(n-3) + 3c = \cdots = T_1(0) + nc = d + cn.$$

By the §18.5 method. The associated homogeneous recurrence is $T_1(n) = T_1(n-1)$, whose characteristic root is 1, giving $T_1^{(h)} = \alpha \cdot 1^n = \alpha$. The forcing term is the constant $c$; but a constant trial particular solution would clash with the homogeneous solution (also a constant — the root is 1). Following the pitfall rule of §18.5, multiply the trial by $n$: try $T_1^{(p)} = An$. Substituting, $An = A(n-1) + c$, so $A = c$, giving $T_1^{(p)} = cn$. Then $T_1(n) = \alpha + cn$, and $T_1(0) = d$ fixes $\alpha = d$. Same answer: $T_1(n) = d + cn$.

🔄 Check Your Understanding The §18.5 method needed the "multiply by $n$" fix here. Why did the naive constant guess clash?

Answer

The associated homogeneous recurrence $T_1(n) = T_1(n-1)$ has characteristic root $r = 1$, so its solutions are the constants. A constant trial particular solution is therefore already a homogeneous solution, and substituting it gives $A = A + c$, i.e. $0 = c$ — a contradiction. Multiplying the trial by $n$ (to $An$) escapes the homogeneous family, and the substitution succeeds.

Verdict for Helper 1: $T_1(n) = d + cn = O(n)$ — linear. Doubling the input doubles the work. Perfectly healthy for a function that has to look at every element.

Phase 2: Helper 2 — two calls on nearly-full inputs

Now the suspicious one. First, separate two recurrences that look alike but mean different things.

The value score_paths(n) computes satisfies $v_n = v_{n-1} + v_{n-2}$ with $v_0 = 1$ and (treating the negative branch) $v_1 = 1$ — this is the Fibonacci recurrence (it counts ordered sums of 1s and 2s, the very object of §18.2's Productive Struggle). So score_paths(5) $= 8$, matching the test ($v_2=2, v_3=3, v_4=5, v_5=8$).

But the question is cost, and the running time obeys its own recurrence. Let $T_2(n)$ count the calls (each call does $O(1)$ work outside its recursive calls). A call with $n \ge 1$ makes one call on $n-1$ and one on $n-2$, plus itself:

$$T_2(n) = T_2(n-1) + T_2(n-2) + c.$$

This is the Fibonacci recurrence plus a constant — the last row of the §18.6 table. We do not need a perfect closed form to make the engineering call; we need the growth rate, and §18.6 already told us how to get it: drop the additive constant and recognize the homogeneous Fibonacci core, whose solutions grow like $\phi^n$ with $\phi = \frac{1+\sqrt5}{2} \approx 1.618$ (the golden ratio Chapter 19 derives). Concretely, $T_2(n) \ge v_n = F_{n+1}$, and $F_{n+1}$ grows like $\phi^{\,n}$.

To see the explosion without the closed form, count calls directly with a tiny instrument.

def score_paths_calls(n):
    """Number of calls score_paths makes to compute score_paths(n)."""
    if n < 0:
        return 1                 # one (base) call on a negative argument
    if n == 0:
        return 1                 # one (base) call
    # one call here, plus all calls of the two recursive subcalls:
    return 1 + score_paths_calls(n - 1) + score_paths_calls(n - 2)

print([score_paths_calls(n) for n in range(0, 11)])
# Expected output:
# [1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287]

We hand-trace the first few to trust the rest. $C_0 = 1$, and for $n=1$ the recursion hits the $n=0$ branch and the $n=-1$ branch: $C_1 = 1 + C_0 + C_{-1} = 1 + 1 + 1 = 3$. Then $C_2 = 1 + C_1 + C_0 = 1 + 3 + 1 = 5$; $C_3 = 1 + C_2 + C_1 = 1 + 5 + 3 = 9$; $C_4 = 1 + 9 + 5 = 15$; $C_5 = 1 + 15 + 9 = 25$. The list above continues that pattern, and the call count itself satisfies $C_n = C_{n-1} + C_{n-2} + 1$ — a nonhomogeneous Fibonacci recurrence whose homogeneous part forces exponential growth.

💡 Intuition: The two recurrences — for the value and for the cost — have the same shape because the function makes one call on $n-1$ and one on $n-2$, and the time to handle each subproblem is itself $T_2$ of that smaller size. "Same recurrence ⇒ same growth": the running time grows like the Fibonacci numbers it is computing. That is the precise reason naive Fibonacci-style recursion is unusable.

Project the cost. With $\phi \approx 1.618$, going from $n = 30$ to $n = 60$ multiplies the call count by about $\phi^{30} \approx 1.6 \times 10^6$. A request that took 1 ms at $n=30$ takes roughly half an hour at $n=60$. This is the function that times out.

Verdict for Helper 2: $T_2(n)$ grows like $\phi^n$ — exponential. Correct, and catastrophically slow.

Phase 3: Helper 3 — linear work, but the input halves

Helper 3 is the subtle case, and it is a deliberate trap for the eye. It does a linear scan (clearly expensive) but then recurses on half the input. Which effect wins?

Let $T_3(n)$ be its running time. The scan costs about $cn$; then one recursive call on $\lfloor n/2 \rfloor$. So:

$$T_3(n) = T_3(n/2) + cn, \qquad T_3(1) = d.$$

This is a divide-and-conquer recurrence — the input shrinks by a factor, not by a constant — and that kind does not fit the characteristic-equation method of §18.4. (The book is explicit about this: §18.6 flags binary search's $T(n) = T(n/2) + c$ as Chapter 19's territory, solved by the Master Theorem.) But we can still unroll it by hand to get the answer, which is all the forensics needs. Assume $n$ is a power of 2, $n = 2^m$:

$$T_3(n) = cn + T_3(n/2) = cn + \tfrac{cn}{2} + T_3(n/4) = cn + \tfrac{cn}{2} + \tfrac{cn}{4} + \cdots$$

The scan costs halve at each level: $cn + cn/2 + cn/4 + \cdots$. That is a geometric series (Chapter 11) with ratio $1/2$, and even summed to infinity it is at most $cn \cdot \frac{1}{1 - 1/2} = 2cn$. So $T_3(n) \le 2cn + d = O(n)$.

⚠️ Common Pitfall: The instinct "it has a loop and recursion, so it must be slower than the loop-free Helper 1" is wrong. Because the input halves, the per-level scan cost collapses geometrically; the top level's scan dominates, and the total is still linear. The recurrence exposes this; eyeballing the code does not. (Contrast $T_3(n) = T_3(n-1) + cn$, which shrinks by one and sums to $O(n^2)$ — exercise 18.25. The difference between "$-1$" and "$/2$" is the difference between quadratic and linear here.)

def depth_report_work(n):
    """Units of scan-work depth_report does on input n (sum of the per-level scans)."""
    if n <= 1:
        return 0
    return n + depth_report_work(n // 2)   # this level's scan + the recursive level

print([depth_report_work(n) for n in [1, 2, 4, 8, 16, 32]])
# Expected output:
# [0, 2, 6, 14, 30, 62]

Hand-check: $W(8) = 8 + W(4) = 8 + (4 + W(2)) = 8 + 4 + (2 + W(1)) = 8 + 4 + 2 + 0 = 14$, matching the unit test's 8 + 4 + 2. And $W(2^m) = 2^{m+1} - 2 = 2n - 2$, the geometric-series closed form — squarely $O(n)$, confirming the unrolling.

Verdict for Helper 3: $T_3(n) = O(n)$ — linear, despite the loop. Healthy.

Phase 4: Rank, decide, and fix the one that matters

Lay the three verdicts side by side — this is the table the engineer takes to the team.

The forensics is conclusive without a profiler: Helper 2's running time grows like the golden ratio raised to the $n$, and nothing else does. Now — and only now — fix it. The standard repair is memoization: cache each score_paths(k) so the overlapping subproblems are solved once. That collapses the two-call tree into $n$ distinct subproblems, each $O(1)$ after the first, turning the cost recurrence into $T(n) = T(n-1) + c = O(n)$ — the very recurrence of healthy Helper 1.

def score_paths_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n < 0:
        return 0
    if n == 0:
        return 1
    if n in cache:
        return cache[n]
    cache[n] = score_paths_memo(n - 1, cache) + score_paths_memo(n - 2, cache)
    return cache[n]

print(score_paths_memo(5))    # same value as before
print(score_paths_memo(50))   # now instant; naive version would never finish
# Expected output:
# 8
# 20365011074

The value $20{,}365{,}011{,}074$ is $F_{51}$ — the 51st Fibonacci number (with $F_0 = 0$) — which we can state because score_paths(n) $= F_{n+1}$ and $F_{51}$ is the standard value; the memoized version computes it in $O(n)$ time, while the naive version's $\phi^{50} \approx 2 \times 10^{10}$ calls would hang the service. The recurrence diagnosed the disease; the recurrence also certified the cure.

🚪 Threshold Concept: Once "code → recurrence → growth rate" is automatic, performance stops being something you measure after the fact and becomes something you predict from the source. The profiler confirms; the recurrence explains. An engineer who can do this triages three suspect functions in the time it takes to write their recurrences on a whiteboard — which is exactly what just happened.

Discussion Questions

1. We deliberately excluded the cost of Python's list slicing xs[1:] from Helper 1's recurrence. Slicing copies the tail, which is itself $O(n)$ work. Rewrite the recurrence to include it ($T_1(n) = T_1(n-1) + cn$) and solve it. What growth rate does the real list_sum have, and what one-line change to the code (passing an index instead of a slice) restores $O(n)$? Tie this to the §18.6 note about preferring an index parameter.
2. Helper 2's value recurrence and cost recurrence have the same shape but different initial conditions. Does the choice of initial conditions change the growth rate? Why or why not? (Relate to §18.4: the constants $\alpha, \beta$ fit the initial conditions, but the roots — hence the growth — come from the recurrence alone.)
3. For Helper 3 we assumed $n$ was a power of 2 to unroll cleanly. Argue informally that the $O(n)$ conclusion still holds for general $n$ (sandwich $n$ between two powers of 2). Why is "assume a power of 2" a safe simplification for growth-rate purposes but not for an exact count?
4. The memoized fix turned $T_2$ from exponential to linear. State the new recurrence precisely and identify which §18.6 table row it now matches. What did memoization do to the recursion tree that made the two-term recurrence collapse to a one-term recurrence?

Your Turn: Extensions

• Option A (a fourth suspect). A teammate adds def split_check(n) that makes two recursive calls, each on $n/2$, plus an $O(n)$ scan: $T_4(n) = 2T_4(n/2) + cn$. Unroll it by hand for $n$ a power of 2 (you will get $\log_2 n$ levels, each costing $cn$) and conjecture its growth. This is the merge-sort recurrence; confirm your conjecture against Chapter 19's preview of $O(n \log n)$ in §18.6, and note that the characteristic-equation method does not reach it.
• Option B (instrument and tabulate). Using the call-counting pattern of score_paths_calls, write call counters for all four helpers, hand-trace them for $n = 1, 2, 4, 8, 16$, and assemble a table of call counts. Verify that the ratios match the growth rates you derived (constant-factor growth for the linear ones, $\approx \phi$ per step for Helper 2).
• Option C (the Toolkit angle). Use solve_linear from this chapter's Project Checkpoint to compute score_paths(n)'s value for $n$ up to 40 via the recurrence $[1,1]$ with appropriate initial conditions, and confirm it agrees with score_paths_memo. Explain why solve_linear (an $O(nk)$ unroller) is fast here even though the naive recursion is exponential — what is solve_linear doing that the naive recursion is not?

Key Takeaways

1. The recurrence is the cost, made visible. Reading $T(n)$ off the code and solving it ranks three suspects by growth rate before any profiler runs — linear, linear, exponential.
2. Value and cost obey different recurrences. score_paths computes Fibonacci and costs Fibonacci; recognizing the cost recurrence's shape is what flags the exponential blow-up.
3. Shape, not loops, decides growth. A function with a loop and recursion (Helper 3) can still be linear when the input halves; the geometric series of shrinking scan-costs collapses to $O(n)$.
4. Diagnose with the method that fits. First-order constant-forcing recurrences solve by §18.5; divide-and-conquer ones ($T(n/2)$, $2T(n/2)$) need Chapter 19 — but even those you can unroll to a verdict. The exponential Fibonacci-shaped one is the disease; memoization is the cure, and it turns the cost recurrence back into a healthy linear one.