Recursion and Backtracking
A recursive function solves a problem by calling itself on a smaller input. Every recursion needs a base case and progress towards it.
factorial.py
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1)
Memoisation
Cache results to turn exponential recursion into linear time.
fib.py
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2) # O(n)
Backtracking: subsets
Choose, explore, un-choose.
subsets.py
def subsets(nums):
result, path = [], []
def dfs(i):
if i == len(nums):
result.append(path[:])
return
dfs(i + 1) # skip nums[i]
path.append(nums[i]) # choose
dfs(i + 1) # explore
path.pop() # un-choose
dfs(0)
return result # 2^n subsets
CAUTION
Python's default recursion limit is about 1000 frames. For deep recursion, convert to an explicit stack or loop.
Loading Comments...