The dynamic programming factorial in this repo performs one heap allocation per call, 52 bytes, and throws it away before it returns. The recursive version it replaced performs none.

Here is the shipped version:

pub fn factorial(n: i32) -> i32 {
    // recursive
    // match n {
    //     0 => 1,
    //     1 => 1,
    //     _ => n * Self::factorial(n - 1),
    // }
    // dynamic programming
    let mut memo = vec![1; (n + 1) as usize];
    for i in 2..=n as usize {
        memo[i] = memo[i - 1] * i as i32;
    }
    memo[n as usize]
}

The recursive version it replaced is right there, commented out, and it is four lines. The version that shipped is six lines and does more work.

memo is not a memo

The variable is named memo, and the comment says “dynamic programming,” but neither is true of what the code does. Memoization exists to avoid computing the same value twice. Factorial never computes the same value twice. There is exactly one call path, n! depends on (n-1)! depends on (n-2)!, and each of those is computed once. Nothing is reused, so there is nothing to memoize.

The table exists to hold intermediate values that are read exactly once, immediately, by the very next iteration. memo[i] is written, then read as memo[i - 1] on the next pass. A single variable holds the same information:

let mut acc = 1;
for i in 2..=n {
    acc *= i;
}

That is the whole computation. The table is n+1 slots to carry one number forward.

Counting allocations instead of timing

The robust measurement is the one that does not depend on how busy the machine is. I swapped in a counting global allocator and counted allocations per call at n = 12:

over 1000 calls at n=12:
vec table   : 1000 allocations, 52000 bytes
accumulator : 0 allocations
recursive   : 0 allocations
bytes per vec call = 52

The shipped version performs exactly one heap allocation per call and then throws it away. The other two versions perform none. That is not a benchmark, it is a count, and it does not change when the machine is busy.

The wall-clock numbers are less tidy. Across repeated runs of one million iterations on this machine, the Vec version was the slowest of the four in every single sample, but the ratio swung between roughly 9 and 140 times slower than the recursion depending on what else was running. I am not going to quote a single figure from that range as if it meant something precise. The ordering was consistent; the magnitude was not.

What isolates the allocation cleanly is to run the same algorithm with the table on the stack instead of the heap:

let mut memo = [1i32; 64];
for i in 2..=n as usize {
    memo[i] = memo[i - 1] * i as i32;
}
memo[n as usize]

Same loop, same arithmetic, same result, zero allocations. In every one of my runs this version was dramatically faster than the Vec version, and it was never slower.

So the “optimization” is not the table. It is the allocation. And I added the allocation.

The recursion does not recurse in release

The honest comparison is not table-against-recursion in raw bytes. I measured both with a counting allocator and a stack-address probe at n = 12:

dp table   : answer 479001600, HEAP bytes = 52
recursive  : answer 479001600, STACK bytes = 976

The recursion uses more raw bytes, because each frame carries its own locals and return address. What the recursion does not do is allocate. And in a release build it does not even recurse. LLVM converts n * factorial(n - 1) into a loop, because the recursion is a tail call in everything but name and the multiplication is the only thing left to do. I confirmed this by measuring the stack pointer at the bottom of the recursion:

### DEBUG ###
recursive  : answer 479001600, STACK bytes = 976
### RELEASE ###
recursive  : answer 479001600, STACK bytes = 0

Zero stack in release. The optimizer turned the recursion into a loop and there is no recursion left to overflow a stack. I confirmed this two ways. The disassembly of the release binary contains no self-call in that function at all, only a backward branch inside the function body; the debug binary contains two. And a release build survives a recursion depth of one million on an eight-kilobyte thread stack, which is impossible for one frame per level:

stack 8 KiB, depth 100000  -> OK (returned 0)
stack 8 KiB, depth 1000000 -> OK (returned 0)

The comment I left in the file, promising a “recursive” implementation, describes code that does not run in a release build.

The overflow I added

The one thing the table version has that the recursion does not is n + 1:

let mut memo = vec![1; (n + 1) as usize];

That addition overflows when n == i32::MAX, and nothing in the recursive version ever computes n + 1. Debug build:

thread 'main' panicked at src/main.rs:16:32:
attempt to add with overflow

Release build:

thread 'main' panicked at .../library/alloc/src/raw_vec/mod.rs:28:5:
capacity overflow

Two different panics from the same line. In release the addition wraps silently to i32::MIN, and then (n + 1) as usize turns that into 18446744071562067968, and the allocation of a buffer that large fails the allocator’s capacity check rather than the arithmetic check. The overflow moved; it did not go away.

To be clear about the spec: the constraint is 0 <= n <= 12, so n == i32::MAX is out of range and none of this is a violation of the problem. It is a shape in the code, not a bug that ships. But it is the shape I introduced by choosing the table.

The version I would keep

Neither of the two versions in the file is what I would write. This is mine:

pub fn factorial(n: i32) -> i32 {
    let mut acc: i64 = 1;
    for i in 2..=n as i64 {
        acc *= i;
    }
    acc as i32
}

The i64 accumulator is the part that matters. 12! is 479001600, which fits in an i32, but 13! is 6227020800, which does not, and the constraint stops at 12 for exactly that reason. Widening the accumulator moves the overflow to the one place it cannot be mistaken for arithmetic: the final as i32. One step past the constraint, this version returns 1932053504 in both profiles, where the shipped version panics in debug and returns the same number in release. The truncation is still wrong, but it is now a single explicit narrowing on the return line instead of a per-iteration multiply that nobody was watching.

I like that the repository keeps the recursion commented out instead of deleting it. The comment is the record of the decision, and it is the reason I could tell you which version was faster without guessing.

I just do not think the decision it records was right, and I am writing this down so the next swap is not another one. The rule I am taking from it: when I replace a loop with a table, I count allocations before I count milliseconds. A table that allocates is not memoization, it is a slower way to hold one number, and the allocation count says that in a way the timing does not.


Next: Three Implementations, One Shipped