Recursion, Backtracking, and Dynamic Programming
Thinking recursively
Recursion as self-similar problem solving
A recursive solution solves a problem by calling itself on smaller versions of the same problem. Good recursive designs define a base case, a recursive step, and a measure that guarantees progress toward the base case.
The three recursion checks
Ask: What is the base case? How does the problem get smaller? Why does it terminate?
What is the base case in recursion?
The base case prevents infinite recursion.
Correct answer: The stopping condition
Why is a base case necessary?
Termination is essential for correctness.
Correct answer: It ensures the recursive process stops instead of continuing forever.
Backtracking and search
Backtracking explores choices incrementally and abandons partial solutions that cannot lead to success. It is useful for puzzles, constraint problems, and exhaustive search. Although it can be expensive, pruning can dramatically reduce the search space.
Dynamic programming
Dynamic programming solves optimization problems by reusing results of overlapping subproblems. Memoization stores results top-down, while tabulation builds solutions bottom-up. The key idea is to avoid repeated work.
Dynamic programming is especially useful when a problem has:
DP works well when subproblems repeat and solutions can be combined optimally.
Correct answer: Overlapping subproblems and optimal substructure
What is memoization?
Memoization prevents repeated computation.
Correct answer: Storing the results of expensive function calls so they can be reused later.
How to approach a DP problem
-
1
Step 1: Define the state clearly.
-
2
Step 2: Identify the recurrence relation.
-
3
Step 3: Determine base cases.
-
4
Step 4: Choose memoization or tabulation.
-
5
Step 5: Analyze time and space complexity.