Recursion

Question 1

What are indicators that a problem needs to be solved with recursion?

Answer 1

• When I can break it into subproblems
• When there is some sort of repetition
• When a recursive data structure is involved
• Trees and BST (almost always you should think about recursion)
• Array or List: A[0..N] = A[0] + A[1..n] or A[0..mid] + A[mid+1..N]

Question 2

How do I solve a recursion problem?

Answer 2

You need to answer these questions clearly:

A. Find the recursive relationship

B. What are the subproblems?

C. How do we combine them?

D. What is the base case?

E. Try to draw the recursion tree.
Root: is the overall problem
Children of the root: subproblems
Leaves: Base cases

Question 3

What are some famous recursion problems?

Answer 3

Famous:
- nth Fibonacci
- POW (power) problem
- Factorial problem
- Any tree traversal
- Binary search
- merge sort
- coin change

Question 4

What is the key insight about recursion?

Answer 4

Every recursive function is really DFS on the recursion tree
Recursion -> DFS -> Recursion

Question 5

What is the template for a recursion problem?

Answer 5

def dfs(state):
# IMPLEMENT base case

if …is_basecase(state):
return …

IMPLEMENT recursive formula
ans = …combine(dfs(branch_1),dfs(branch_2), …)

return ans

Question 6

What is the runtime and space complexity of a Recursion problem?

Answer 6

Runtime: O(n) where n is the number of nodes in the recursion tree (assuming combine function can be done in constant time)

For Fibonacci:
Runtime = O(2^n)
For merge sort:
MS(arr, left, right) =MS(arr, left, mid), MS(arr, mid+1, right)

T(n) = 2*T(n/2) + O(n): this can be proven to be O(n log n)

Memory: O(h) // height of recursion tree