7.
Recursion and Backtracking
Recursion is a powerful concept in programming where a function calls itself to solve smaller
subproblems of a larger problem. Backtracking is a technique used to explore all possible
solutions by making choices and undoing them when needed.
🚀 1. What is Recursion?
📌 Definition: Recursion is a method where a function calls itself until a base condition is met.
🔹 Basic Structure of Recursion
def recursive_function():
if base_condition:
return result # Stop recursion (base case)
else:
return recursive_function() # Recursive call
🔥 2. Tail Recursion vs Normal Recursion
🔹 Normal Recursion: Recursive calls stay in memory until all calls are completed.
🔹 Tail Recursion: The recursive call is the last operation in the function, so it can be
optimized by compilers to avoid excessive memory usage (Tail Call Optimization - TCO).
✅ Example: Normal Recursion (Factorial)
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1) # Recursive call is NOT the last
operation
print(factorial(5)) # Output: 120
✅ Example: Tail Recursion (Optimized)
def tail_factorial(n, accumulator=1):
if n == 0:
return accumulator
return tail_factorial(n - 1, accumulator * n) # Recursive call is
the last operation
print(tail_factorial(5)) # Output: 120
🎯 3. Problems Solved Using Recursion
🔥 A. Factorial of a Number
Factorial of n is n! = n × (n-1)!.
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # Output: 120
🔥 B. Fibonacci Sequence
Each number is the sum of the two previous numbers:
F(n) = F(n-1) + F(n-2)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6)) # Output: 8
⚡ Optimization: Use memoization (DP) for O(n) complexity.
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6)) # Output: 8
🔥 C. Tower of Hanoi
A classic problem where we move n disks from source → destination using an auxiliary
peg.
Steps:
11 Move n-1 disks from Source → Auxiliary
1️⃣
2️⃣Move 1 disk from Source → Destination
3️⃣Move n-1 disks from Auxiliary → Destination
def tower_of_hanoi(n, source, auxiliary, destination):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n - 1, source, destination, auxiliary)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n - 1, auxiliary, source, destination)
tower_of_hanoi(3, 'A', 'B', 'C')
📌 Time Complexity: O(2^n) (Exponential)
🔥 D. N-Queens Problem (Backtracking)
The goal is to place N queens on an N×N chessboard such that no two queens attack each
other.
def is_safe(board, row, col, n):
# Check column
for i in range(row):
if board[i] == col:
return False
if abs(board[i] - col) == abs(i - row): # Check diagonals
return False
return True
def solve_n_queens(n, row=0, board=[]):
if row == n:
print(board) # Solution found
return
for col in range(n):
if is_safe(board, row, col, n):
board.append(col)
solve_n_queens(n, row + 1, board)
board.pop() # Backtrack
solve_n_queens(4) # Example for N=4
📌 Time Complexity: O(N!)
🔥 E. Sudoku Solver (Backtracking)
Fill a 9×9 Sudoku board by placing numbers 1-9 without breaking Sudoku rules.
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
box_x, box_y = row - row % 3, col - col % 3
for i in range(3):
for j in range(3):
if board[box_x + i][box_y + j] == num:
return False
return True
def solve_sudoku(board, row=0, col=0):
if row == 9:
return True
if col == 9:
return solve_sudoku(board, row + 1, 0)
if board[row][col] != 0:
return solve_sudoku(board, row, col + 1)
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board, row, col + 1):
return True
board[row][col] = 0 # Backtrack
return False
📌 Time Complexity: O(9^N) (N = empty cells)
🔥 F. Rat in a Maze (Backtracking)
A rat moves in a N×N maze from (0,0) → (N-1,N-1), only moving right (R) or down (D).
def solve_maze(maze, x, y, path, n):
if x == n - 1 and y == n - 1: # Reached destination
print(path)
return
# Move Right
if y + 1 < n and maze[x][y + 1] == 1:
solve_maze(maze, x, y + 1, path + "R", n)
# Move Down
if x + 1 < n and maze[x + 1][y] == 1:
solve_maze(maze, x + 1, y, path + "D", n)
# Example Maze
maze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
solve_maze(maze, 0, 0, "", 4)
📌 Time Complexity: O(2^(N^2))
🎯 Key Takeaways for Placements
✅ Recursion helps in problems with repetitive subproblems (Fibonacci, Factorial,
Hanoi).
✅ Backtracking is used for decision-making problems (N-Queens, Sudoku, Rat in a
Maze).
✅ Tail Recursion is optimized by compilers, but Python does NOT support TCO.
🔥 Best Practice: Use memoization or iterative approaches when recursion depth is high! 🚀
8. Dynamic Programming (DP)
Dynamic Programming (DP) is a powerful algorithmic technique used to solve problems by
breaking them into smaller overlapping subproblems and solving each only once to improve
efficiency.
🎯 1. Introduction to Dynamic
Programming (DP)
📌 Definition: DP is an optimization technique where we store already computed results to
avoid redundant calculations, making algorithms faster and more efficient.
📌 When to use DP?
✔ Optimal Substructure – The problem can be broken into smaller subproblems that have
optimal solutions.
✔ Overlapping Subproblems – The same subproblem is solved multiple times (e.g.,
Fibonacci).
📌 Approaches to Solve DP Problems
✅ Top-Down (Memoization) – Solve problems recursively and store results.
✅ Bottom-Up (Tabulation) – Solve problems iteratively and build up solutions.
🔥 2. Difference Between Memoization and
Tabulation
Feature Memoization (Top-Down) Tabulation (Bottom-Up)
Approach Recursion + Caching Iterative
Storage Uses a hash table (dict) or array Uses a table (array)
Function Calls Many recursive calls No recursion
Efficiency Can be slow due to recursion Usually faster (no recursion
overhead overhead)
🎯 3. Common DP Problems & Solutions
🔥 A. Fibonacci Using DP
Normal Recursion (Exponential Time Complexity O(2^n))
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6)) # Output: 8
❌ Inefficient for large values of n
✅ Optimized Using Memoization (Top-Down Approach)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100)) # Output: 354224848179261915075
⏳ Time Complexity: O(n), Space Complexity: O(n)
✅ Optimized Using Tabulation (Bottom-Up Approach)
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib(100)) # Output: 354224848179261915075
⏳ Time Complexity: O(n), Space Complexity: O(n)
🚀 Further Optimization (Constant Space O(1))
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(100)) # Output: 354224848179261915075
🔥 B.
0/1 Knapsack Problem
Given N items, each with a weight and value, and a bag with maximum weight W, determine
the maximum value we can carry.
📌 Recursion (Exponential O(2^n))
def knapsack(wt, val, W, n):
if n == 0 or W == 0:
return 0
if wt[n - 1] <= W:
return max(val[n - 1] + knapsack(wt, val, W - wt[n - 1], n -
1),
knapsack(wt, val, W, n - 1))
return knapsack(wt, val, W, n - 1)
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W, len(weights))) # Output: 7
❌ Inefficient for large n
✅ Optimized Using DP (Tabulation - O(nW))
def knapsack(wt, val, W, n):
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if wt[i - 1] <= w:
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]],
dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
print(knapsack(weights, values, W, len(weights))) # Output: 7
⏳ Time Complexity: O(nW), Space Complexity: O(nW)
🔥 C. Longest Common Subsequence (LCS)
Find the longest subsequence common to two strings (not necessarily contiguous).
📌 Recursion (O(2^n))
def lcs(x, y, m, n):
if m == 0 or n == 0:
return 0
if x[m - 1] == y[n - 1]:
return 1 + lcs(x, y, m - 1, n - 1)
return max(lcs(x, y, m - 1, n), lcs(x, y, m, n - 1))
print(lcs("abcde", "ace", 5, 3)) # Output: 3
✅ Optimized Using DP (O(m×n))
def lcs(x, y):
m, n = len(x), len(y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs("abcde", "ace")) # Output: 3
🔥 D. Matrix Chain Multiplication
Given a sequence of matrices, find the most efficient way to multiply them.
✅ Optimized DP Solution (O(n³))
import sys
def matrix_chain_order(p, i, j):
if i == j:
return 0
dp = [[0 for _ in range(j + 1)] for _ in range(j + 1)]
for l in range(2, j + 1):
for i in range(1, j - l + 2):
k = i + l - 1
dp[i][k] = sys.maxsize
for m in range(i, k):
cost = dp[i][m] + dp[m + 1][k] + p[i - 1] * p[m] *
p[k]
dp[i][k] = min(dp[i][k], cost)
return dp[1][j]
arr = [1, 2, 3, 4]
print(matrix_chain_order(arr, 1, len(arr) - 1)) # Output: 18
E. Subset Sum Problem
Problem Statement
Given a set of N positive integers and a target sum S, determine whether there exists a subset
whose sum is exactly S.
📌 Example:
Input: arr = [3, 34, 4, 12, 5, 2], S = 9
Output: True
Explanation: The subset {4, 5} adds up to 9.
🛠 1. Brute Force Solution (Recursion) -
Exponential O(2^N)
✔ Approach:
● For each element, we have two choices:
○ Include it in the subset and reduce the target (S - arr[i]).
○ Exclude it and move to the next element.
● Base Case:
○ If S == 0, return True (subset found).
○ If N == 0 and S != 0, return False (no subset possible).
✅ Python Code:
def subset_sum(arr, n, S):
if S == 0:
return True
if n == 0:
return False
if arr[n - 1] > S:
return subset_sum(arr, n - 1, S)
return subset_sum(arr, n - 1, S) or subset_sum(arr, n - 1, S -
arr[n - 1])
arr = [3, 34, 4, 12, 5, 2]
S = 9
print(subset_sum(arr, len(arr), S)) # Output: True
⏳ Time Complexity: O(2^N) (Exponential, very slow for large inputs)
❌ Inefficient for large N, leads to repeated computations.
🔥 2. Optimized Solution Using Dynamic
Programming (DP) - O(N * S)
✔ Approach:
● Use a DP table dp[i][j] where:
○ i represents the first i elements.
○ j represents the sum we want to achieve.
● Base Cases:
○ dp[0][j] = False (No elements → No sum except 0).
○ dp[i][0] = True (Sum 0 can be achieved with an empty subset).
● Recurrence Relation:
○ If the element is greater than j, we exclude it:
dp[i][j] = dp[i-1][j]
○ Otherwise, we include or exclude the element:
dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]]
✅ Python Code (Tabulation Approach)
def subset_sum(arr, S):
n = len(arr)
dp = [[False] * (S + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True # Sum 0 is always possible (empty subset)
for i in range(1, n + 1):
for j in range(1, S + 1):
if arr[i - 1] > j:
dp[i][j] = dp[i - 1][j] # Exclude element
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
# Include or exclude
return dp[n][S]
arr = [3, 34, 4, 12, 5, 2]
S = 9
print(subset_sum(arr, S)) # Output: True
⏳ Time Complexity: O(N * S)
📌 Space Complexity: O(N * S)
🚀 3. Space Optimized DP - O(S) Space
Complexity
Instead of using a 2D array (dp[n][S]), we use a 1D array (dp[S]).
✅ Python Code (Space Optimized DP)
def subset_sum(arr, S):
n = len(arr)
dp = [False] * (S + 1)
dp[0] = True # Base case: sum 0 is always possible
for num in arr:
for j in range(S, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[S]
arr = [3, 34, 4, 12, 5, 2]
S = 9
print(subset_sum(arr, S)) # Output: True
⏳ Time Complexity: O(N * S)
📌 Space Complexity: O(S)
🎯 Key Takeaways for Placements
✅ Brute Force (Recursion) - O(2^N) → Exponential (Bad for large N).
✅ DP Table (O(N*S)) - Tabulation Approach → Faster & avoids redundant
work.
✅ Space Optimization (O(S)) → Efficient memory usage.
✅ Used in Knapsack-type problems → Important for DP-based interview
questions!
🎯 Key Takeaways for Placements
✅ Recognize DP problems (Optimal Substructure + Overlapping Subproblems).
✅ Use Memoization for recursive problems and Tabulation for iterative solutions.
✅ Optimize space complexity where possible (e.g., Fibonacci O(1) space).
🔥 Mastering DP is a game-changer for coding interviews! 🚀
