Recall, the recursive function for calculating the n^th term of the Fibonacci sequence exhibits an algorithmic runtime complexity that is exponential; this means that as the input grows, the time to complete the function grows exponentially. Attempting to calculate the 20^th Fibonacci number recursively would take an unreasonably long amount of time. In general, algorithms that exhibit such runtime complexity are best avoided if possible. The main reason for the inefficiency in the Fibonacci algorithm is the repeated computations of the same number. We can remedy this issue by saving any previously computed value in a data structure with preferably fast look-up and insertion time, thereby avoiding having to compute the same value again. The ideal data structures for this operation are an array or a hash table. This technique is called memoization. The general template for applying dynamic programming to optimize a recursive function is:

1. Inspect the memo table (array or hash table) to determine if the recursive function has been called for some input n. If the memo table contains an entry for n, this means that the value for n has been previously computed so return that value as opposed to computing it again. If there is no entry for n, proceed to step two.
2. Compute the value recursively and store it in the memo table.
3. Return computed value.

The structure of the memo table needed for memoization is defined by the return type of the recursive function as well as the number and type of its input parameters. For example, the function to calculate the Fibonacci sequence accepts one number and returns one number, therefore the data structure needed to store the previously computed values should map one number to another number.

The template for an optimized recursive function in Python is:

def recursive(a, b ,c, memo_table):  
  # Check memo_table first. Return value corresponding to the inputs given if it is in memo_table. If not, proceed
  # Compute value here. You will have to call “recursive(x, y, z, memo_table)” at some point
  # Store value in memo_table
  # Return computed value

memo = {} # memo_table containing previous values should be 3-dimensional because of recursive function input params

The most common data structure used for the memo_table in Python is a dictionary.