Know this before you start: “Simulate recursion with an explicit stack”
Replacing recursion with your own stack
Recursion uses the call stack behind the scenes. Pushing work onto your own stack does the same job without recursion limits.
The idea
Every recursive call waits on the call stack until its sub-calls finish. You can do the same yourself: push the work still to do, pop one item, process it, push its sub-work.
This avoids Python's recursion limit (about 1,000 calls deep) and makes the order of work explicit. Depth-first search on trees and graphs is the classic use.
See it step by step
Sum a nested list [1, [2, [3, 4]], 5] without recursion
- stack = [the whole list]. Pop it: push 1, [2, [3, 4]], 5.
- Pop 5 → total 5. Pop [2, [3, 4]] → push 2 and [3, 4].
- Pop [3, 4] → push 3, 4. Pop 4, 3, 2, 1 → total 15.
In code (Python)
def nested_sum(items):
total = 0
stack = [items]
while stack:
current = stack.pop()
if isinstance(current, list):
stack.extend(current) # do its parts later
else:
total += current
return total
def dfs_order(graph, start):
seen, stack, order = {start}, [start], []
while stack:
node = stack.pop()
order.append(node)
for nxt in reversed(graph[node]):
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return order
print(nested_sum([1, [2, [3, 4]], 5])) # 15
print(dfs_order({1: [2, 3], 2: [4], 3: [], 4: []}, 1)) # [1, 2, 4, 3]Same as the recursive version: O(n) time and O(depth) space.
When you'll use it
- Deep trees or graphs where recursion might overflow, iterative tree traversals, decoding nested strings.
Common mistakes
- Forgetting a stack pops the most recent item, so push children in reverse to visit them in order.
- Not marking nodes visited in graphs.
