Learn

Recall, the recursive function for calculating the nth 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 20th 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.

Instructions

1.

In the previous exercise, you wrote a modified Fibonacci sequence function (mod_fib()) in which a number in the sequence is the sum of the previous three numbers. In this checkpoint and the next, you will optimize the mod_fib() function using dynamic programming.

The dictionary memo_fib is provided for you to use as the memo table for the optimized mod_fib() function. Your task is to initialize the dictionary by putting in the initial conditions of the modified Fibonacci sequence.

The initial conditions (base cases) are:

  • F(0) = 0
  • F(1) = 1
  • F(2) = 2

The syntax in Python to map a key to a value in a dictionary is:

dictionary = {key1: value1, key2: value2}
2.

The algorithm to compute the modified Fibonacci sequence recursively is provided in the mod_fib(n) Python function. Use dynamic programming to optimize it.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?