# Factorial using recursion
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
# Fibonacci with recursion and memoization
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print("Factorial of 5:", factorial(5)) # Output: 120
print("Fibonacci of 10:", fib_memo(10)) # Output: 55
Use recursion when a problem naturally decomposes into smaller, similar subproblems.
# Recursive DFS for a graph using an adjacency list
def dfs_recursive(node, visited, graph):
visited.add(node)
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_recursive(neighbor, visited, graph)
# Iterative DFS for a graph
def dfs_iterative(start, graph):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=" ")
# Adding neighbors in reverse order can help mimic recursive DFS
stack.extend(reversed(graph.get(node, [])))
# Sample graph
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("Recursive DFS:")
dfs_recursive('A', set(), graph) # Possible output: A B D E F C
print("\nIterative DFS:")
dfs_iterative('A', graph) # Output order may vary
Use DFS when you need to explore all possible paths, such as in maze traversal or solving puzzles.
from collections import deque
def bfs(start, graph):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Sample graph
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("BFS Traversal:")
bfs('A', graph) # Expected output (level order): A B C D E F
Use BFS when processing nodes level by level, such as in shortest path or level-order tree traversal problems.
# Generate all permutations of a list using backtracking
def permute(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(nums.copy())
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # Choose
backtrack(start + 1) # Explore
nums[start], nums[i] = nums[i], nums[start] # Unchoose (Backtrack)
backtrack(0)
return result
print("Permutations of [1, 2, 3]:")
print(permute([1, 2, 3]))
Use backtracking for problems that require exploring all combinations or configurations, such as N-Queens or Sudoku.
from functools import lru_cache
# Fibonacci with memoization (top-down DP)
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# Fibonacci with tabulation (bottom-up DP)
def fib_tab(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[0], table[1] = 0, 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
print("Fibonacci (memoization) for 10:", fib(10)) # Output: 55
print("Fibonacci (tabulation) for 10:", fib_tab(10)) # Output: 55
Use DP when subproblems overlap. Choose memoization or tabulation based on the nature of the problem.
Recognize the underlying pattern of a DP problem to choose the correct approach and optimize the solution accordingly.