Recursion & DP Target: 15s
Every recursion can be converted to iteration with an explicit stack. Tail recursion converts to a simple loop.
RECURSION → ITERATION CONVERSION
─────────────────────────────────
STEP 1: Identify what the call stack stores
→ Parameters + local variables + return point
STEP 2: Replace call stack with explicit stack
stack = [(initial_params)]
while stack:
params = stack.pop()
# ... process ...
stack.append(next_params) # instead of recursive call
STEP 3: Handle return values
→ Use a result variable or secondary stack
TAIL RECURSION (easy):
# Recursive:
def f(n, acc=0):
if n == 0: return acc
return f(n-1, acc+n)
# Iterative:
acc = 0
while n > 0: acc += n; n -= 1
TREE RECURSION (use stack):
# Recursive: # Iterative:
def dfs(node): stack = [root]
process(node) while stack:
dfs(node.left) node = stack.pop()
dfs(node.right) process(node)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)Type it from memory. Go.