The Memoization Approach: As discussed in your text, page 387, "the idea is to memoize the natural, but inefficient, recursive algorithm. A memorized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it."

A simple recursive function illustrates the approach, such as the recursive definition of Fibonacci numbers:

Memoized Calculation of Fibonacci Numbers

A problem on this week's recitation (Recitation 6) asks you to consider the calculation of C(n,k): the number of combinations of n things taken k at a time. The formula is:

C(n,k) = 1, if k = 0, or if n = k
C(n,k) = C(n-1, k) + C(n-1, k-1), otherwise

You will be asked to write a memoized program to calculate this function.