Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Limitations of Top-Down Dynamic Programming

Understand the drawbacks of top-down dynamic programming, including excessive recursion leading to stack overflow and high execution costs. Learn why loops offer better scalability and prepare for the bottom-up approach that avoids these limitations.

We'll cover the following...

Massive amount of recursion

Top-down dynamic programming consists of recursive calls to the subproblems. The answer is not evaluated until all the subproblems have been evaluated; which in turn depends on their own subproblems. We quickly have a huge number of incomplete recursive calls on our program stack. If we keep making these recursive calls and no previous calls have evaluated; we will run out of space on the stack. This will end up in erroneous termination of the program. Run the following code of the Fibonacci numbers algorithm we discussed in the last chapter.

Python 3.5
memo = {} #dictionary for Memoization
def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  elif n in memo: # Check if result for n has already been evaluated
    return memo[n] # return the result if it is available
  else: # otherwise recursive step
    memo[n] = fib(n-1) + fib(n-2) # store the result of n in memoization dictionary
    return memo[n] # return the value
print (fib(1000))

The program will terminate ...