I counted the calls in the naive recursion that this file keeps in a comment. It makes 2,692,537 calls to produce one number. The version that actually runs allocates nothing.

pub fn fib(n: i32) -> i32 {
    // naive recursion
    // match n {
    //     0 | 1 => n,
    //     _ => Self::fib(n - 1) + Self::fib(n - 2),
    // }
    // memoization
    // if n < 2 {
    //     return n;
    // }
    // let mut memo = vec![0; n as usize + 1];
    // memo[0] = 0;
    // memo[1] = 1;
    // for i in 2..=n as usize {
    //     memo[i] = memo[i - 1] + memo[i - 2];
    // }
    // memo[n as usize]
    // dynamic programming
    if n < 2 {
        return n;
    }
    let mut a = 0;
    let mut b = 1;
    for _ in 2..=n {
        let c = a + b;
        a = b;
        b = c;
    }
    b
}

Three implementations in one function body, two of them comments. This is a design log kept in the source rather than in a commit message or a design doc: a reader who opens the file later can reconstruct the order of the attempts, exponential recursion first, then a table, then two variables. The memoized block even keeps its tail expression, memo[n as usize], which tells you the whole body was replaced rather than patched.

The labels are not quite what they seem. The shipped version is marked // dynamic programming, but the block above it is dynamic programming too. Both compute the same recurrence. The difference is where the state lives: one keeps every value in a vector, the other keeps two.

Counting allocations and calls

I ran all three with a counting allocator and a call counter:

shipped fib(30) = 832040, allocations during the call: 0
memoization fib(30) = 832040, allocations during the call: 1
naive recursion fib(30) = 832040, calls: 2692537

The shipped version allocates nothing at all. It has no vector, no box, no closure. Two integers carry the state and get swapped on each pass of the loop.

The memoization version makes exactly one allocation: vec![0; n as usize + 1], which at n = 30 is 31 i32s, 124 bytes. One allocation is not a problem. It is just not zero, and the reason to prefer the shipped version over the memoized one is precisely that the table is not needed.

The naive recursion is the expensive one. That is 2F(n+1)−12F(n+1) - 1 calls at n = 30, where F(n)F(n) is the nth Fibonacci number and nn is the argument. It is not 2n2^n, because the recursion bottoms out at 0 and 1 rather than at 1, and the number of leaves is the Fibonacci sequence itself. Still exponential, still the wrong shape for this problem.

One line carries the whole range

The shipped version is a handful of lines and one of them carries the whole range of the type:

let c = a + b;

a and b are i32, because the problem’s signature says pub fn fib(n: i32) -> i32. The largest Fibonacci number that fits in an i32 is F(46), which is 1836311903. F(47) is 2971215073, and i32::MAX is 2147483647.

So:

fib(46) = 1836311903

fits, and:

thread 'main' panicked at src/main.rs:13:21:
attempt to add with overflow

is what happens at n = 47 in a debug build. The panic names the addition, and it happens on the last addition of the loop, after forty-five successful ones.

In a release build the same call returns -1323752223 and says nothing at all. That is 2971215073 minus 4294967296, which is what wrapping two’s complement arithmetic does to a number that is too large for the type.

The problem constrains 0 <= n <= 30, so n = 47 is outside the spec and this is not a bug against the problem statement. But the spec is not what enforced the limit. The limit is i32, and it took a debug build and an out-of-spec argument to make it announce itself. The memoized version above has the same arithmetic in the same type and overflows at the same n, one line into its own loop.

The input the file forgets

The comment log is honest about the history and silent about the edges. It records that recursion was too slow and that the table was not needed. It does not record the range of the version it kept, because the type in the signature is the only statement of range in the file, and a type is not a boundary.

So the file remembers every version that was rejected and the reason for the rejection. It does not remember that the version it kept answers correctly up to n = 46 and panics at n = 47.

If I were editing that file today, the line I would add is the one I keep not adding: an assertion at the edge of the type. I would write it before the next implementation lands, not after.


Next: Fifteen Is the Test