Recursion and Dynamic Programming

Question 1

Hints of recursion

Answer 1

It can be built off of sub problems. Look for these problem statements “Design an algorithm to compute the nth…”, “Write code to list the first n…”, “Implement a method to compute all…”

Question 2

Bottom-Up Approach

Answer 2

We start with knowing how to solve the problem for a simple case. Then we figure out how to solve the problem for two elements, then for three elements, and so on. Think about how you can build the solution for one case off of the previous case.

Question 3

Top-Down Approach

Answer 3

Think about how we can divide the problem for case N into sub problems. Be careful of overlap between the cases.

Question 4

Half-and-half approach

Answer 4

Divide the data set in half. Think of binary search and merge sort.

Question 5

Recursive vs. Iterative Solutions

Answer 5

All recursive solutions can be implemented with an interactive solution. Recursive algorithms require at least O(n) space complexity where n is the depth of its recursion tree.

Question 6

Dynamic Programming

Answer 6

Taking recursive problems and finding the overlapping sub problems (that is, the repeated calls). You then cache those results for future recursive calls. Alternatively, you can study the pattern of the recursive calls and implement something iterative. You still cache previous work. Typically used to refer to bottom-up work, but can also refer to top-down work.

Question 7

Memorization

Answer 7

Like dynamic program, it aims to cache repeated calls in a recursive problem. However, it is specific to top-down approach.