Recursion, Backtracking, and
Dynamic Programming
A short guide to recursive thinking, backtracking patterns, and dynamic programming
basics.
1. Recursion Basics
Recursion means a function solves a problem by calling itself on a smaller version of the same
problem. Every recursive solution needs a base case and a recursive case.
Part Meaning Example
Base case When recursion stops n == 0
Recursive case Break problem into smaller problem factorial(n-1)
Call stack Memory of active function calls Each call waits for the next one
Stack overflow Too many recursive calls Missing or unreachable base case
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
Recursion is powerful when the problem naturally branches or repeats: trees, graphs, combinations,
divide-and-conquer, and dynamic programming.
2. Backtracking
Backtracking is recursion with trial and undo. It tries a choice, explores it, and returns if the choice
does not work.
Pattern step Meaning
Choose Pick one possible option
Explore Recursively continue from that choice
Unchoose Undo the choice before trying the next option
Backtracking skeleton
def backtrack(path, choices):
if is_solution(path):
save(path)
return
for choice in choices:
if is_valid(choice, path):
[Link](choice) # choose
backtrack(path, choices) # explore
[Link]() # unchoose
• Common problems: permutations, combinations, Sudoku, N-Queens, maze paths.
• Backtracking can be slow, so pruning bad choices early is important.
3. Dynamic Programming Basics
Computer Algorithms - Quick Guide Page 1
Dynamic programming, or DP, solves problems by reusing answers to smaller subproblems. DP is
useful when recursion repeats the same work many times.
DP idea Meaning Example
Overlapping subproblems Same smaller question appears many Fibonacci
times
Optimal substructure Best answer uses best smaller answers Shortest path, knapsack
Memoization Top-down recursion plus cache Store function results
Tabulation Bottom-up table filling Build dp[0], dp[1], ...
Fibonacci: slow recursion vs memoization
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
The key DP question: What state fully describes the subproblem? Example: dp[i] could mean the answer
using the first i items.
4. Common DP Patterns
Pattern State example Typical problem
1D DP dp[i] Climbing stairs, house robber
2D grid DP dp[row][col] Unique paths, minimum path sum
Knapsack DP dp[i][capacity] Choose items under a limit
String DP dp[i][j] Longest common subsequence, edit distance
Interval DP dp[l][r] Matrix chain multiplication
1D DP skeleton
def climb_stairs(n):
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
DP thinking checklist
• Define the state clearly.
• Write the transition: how does this state use smaller states?
• Set base cases.
• Choose top-down memoization or bottom-up tabulation.
• Check time and space complexity.
5. Practice Questions
• What are the two required parts of a recursive function?
• Why can naive Fibonacci recursion be slow?
• What is the difference between memoization and tabulation?
Computer Algorithms - Quick Guide Page 2
• A robot can move right or down in a grid. Which DP pattern fits?
• In backtracking, why do we undo a choice after recursion?
Answer hints
• Base case and recursive case.
• It repeats the same subproblems many times.
• Memoization is top-down with cache; tabulation is bottom-up with a table.
• 2D grid DP.
• So the next branch starts with a clean state.
Computer Algorithms - Quick Guide Page 3