My blog post Project Euler – Lattice Path (Part 3) showed an implementation of a recursive solution to the lattice path problem in Java.

Major problem was the performance of the algorithm. Working fine for small grids, but lasting forever for the actual 20 x 20 grid.

The recursive nature of the algorithm creates a tree structure.

Unfortunately, already computed values are computed again.

This is no big deal for a 2 x 2 grid. Only the value for (1, 1), which is 2, gets computed twice.

But for a larger grid, walking all tree branches without a sanity check (“Hey, this road looks familiar. I must have been here before.”), the repeated recursive computation causes the performance issue.

For a 3 x 3 grid the values for (2, 1), (1, 1), (2, 2) and (1, 2) have to be computed twice.

For a 4 x 4 grid it’s the values for (3, 1), (2, 1), (1, 1), (3, 2), (2, 2), (1, 2), (3, 3), (2, 3) and (1, 3).

For a 5 x 5 grid…you get the idea.

Pim Spelier introduces an optimization for the recursive algorithm, memoization:

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (Wikipedia)

So let’s try caching.

Et voilà, down to 0 seconds from previously 10+ minutes.