Memoization is the practice of remembering the results of expensive function calls. The first time a function is called with a given set of arguments, it computes the answer and stores it in a table keyed by those arguments; every later call with the same arguments looks the answer up and returns it immediately. A function written this way still reads like an ordinary recursive definition, but it never solves the same instance twice.
The classic motivating example is the recursive computation of Fibonacci numbers. Written naively, the recursion recomputes the same intermediate values an exponential number of times. By storing each Fibonacci value the first time it is computed, the same recursion runs in time proportional to the number of distinct values needed. The MIT 6.006 “Introduction to Algorithms” lecture notes present this recursive-with-memoization approach as the natural starting point for dynamic programming.
Memoization is the top-down face of dynamic programming. A bottom-up dynamic program fills a table of subproblem answers in a carefully chosen order; a memoized recursion instead lets the ordinary call structure drive the work and uses the cache to ensure each subproblem is evaluated only once. The two compute the same answers and have the same asymptotic running time, differing mainly in control flow and in which subproblems actually get touched.
In practice the cache is often a hash table or an array indexed by the function’s arguments. Memoization works well exactly when a problem has overlapping subproblems, the same condition that makes dynamic programming worthwhile; with no repeated calls there is nothing to reuse and the cache only adds overhead.