Recursion and Dynamic Programming

Question 1

What is recursive?

Answer 1

Recursive solutions are built off of solutions to subproblems. You might add, delete or change the previous solution.

Question 2

Bottom-Up Approach

Answer 2

Start with how to solve a simple case, i.g: list with one element [1], then figure out [1,2], then [1,2,3], then [1,2,3,4]….So, the solution can be found from the previous case/multiple previous case

Question 3

Top-Down Approach

Answer 3

• Memoization
• How to divide the problem for case N to subproblems
• Be careful about the overlap of the cases

Question 4

Half-n-Half Approach

Answer 4

• Binary Search: i.g. Looking for an element in a sorted array, we check in the first half, and then recurse look at the other half to see if that array contains the value
• Merge Sort: Sort each half of the array and merge together

Question 5

Recursive vs Iterative Solutions

Answer 5

• Each recursive call adds a new layer to the stack. If the algorithm recurses to a depth of n, it uses at least O(n) memory.
• Implement recursive algorithm iteratively.