Interview Cake by Exponent

Bottom-Up Algorithms

In short: A bottom-up algorithm solves a problem by starting from the smallest subproblems and combining their solutions to build up to the full answer, usually iteratively. It's the iterative counterpart to top-down recursion with memoization in dynamic programming.

Going bottom-up is a way to avoid recursion, saving the memory cost that recursion incurs when it builds up the call stack.

Put simply, a bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards."

For example, if we wanted to multiply all the numbers in the range 1..n, we could use this cute, top-down, recursive one-liner:

def product_1_to_n(n): # We assume n >= 1 return n * product_1_to_n(n - 1) if n > 1 else 1

This approach has a problem: it builds up a call stack of size , which makes our total memory cost . This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.

To avoid this, we can instead go bottom-up:

def product_1_to_n(n): # We assume n >= 1 result = 1 for num in range(1, n + 1): result *= num return result

This approach uses space ( time).

Some compilers and interpreters will do what's called tail call optimization (TCO), where it can optimize some recursive functions to avoid building up a tall call stack. Python and Java decidedly do not use TCO. Some Ruby implementations do, but most don't. Some C implementations do, and the JavaScript spec recently allowed TCO. Scheme is one of the few languages that guarantee TCO in all implementations. In general, best not to assume your compiler/interpreter will do this work for you.

Going bottom-up is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with multiplying the numbers 1..n, above). The other common strategy for dynamic programming problems is memoization.

See also:

Frequently Asked Questions

What is a bottom-up algorithm?

An approach that solves the smallest subproblems first and uses their results to build up to the final answer, typically with iteration rather than recursion.

What's the difference between bottom-up and top-down?

Top-down starts from the full problem and recurses into subproblems (often with memoization); bottom-up starts from the base cases and iterates upward, usually filling a table.

Why use a bottom-up approach?

It avoids recursion overhead and the risk of stack overflow, and it often makes the order of computation and the space usage easier to reason about.

Last updated: June 17, 2026

. . .