Recursion is a stack: converting to an explicit one

Stacks and queues Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

tree = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
order = []
stack = ["a"]
while stack:
    node = stack.pop()
    order.append(node)
    stack.extend(reversed(tree[node]))
print(order)

Options['a', 'b', 'd', 'c']['a', 'c', 'b', 'd']['a', 'b', 'c', 'd']

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A ['a', 'b', 'd', 'c']

Right: pushing children in reverse keeps the recursive pre-order.

The explicit stack reproduces the same visits as the recursive walk, without using the call stack.

Why not the others?

B ['a', 'c', 'b', 'd']. That is the order without reversing the children.
C ['a', 'b', 'c', 'd']. That is level order, which needs a queue.

30-second answer

Every call pushes a frame holding its arguments and local variables; returning pops it. You can do the same by hand: push the starting state onto a list, then loop: pop a state, do its work, and push the states it would have recursed into. This removes the recursion depth limit and makes the stack's memory explicit.

Practise saying it · 45 s. No recording, just a timer

Explain how to replace recursion with a stack.

Say your answer out loud, then check which of these points you covered:

Frames are stack entries
Push states, pop and process
Reverse children for the same order

Deep dive

Push children in reverse order if you need the same visit order as the recursive version.

Post-order work (after the children) needs an extra marker, such as pushing (node, done) pairs.

Generators (yield from) still use recursion; they do not avoid the limit.

Common mistakes

Forgetting that the explicit stack can still use O(n) memory.
Changing the visit order by pushing children in the natural order.

Senior take & follow-ups

Mention that you can convert if the depth is a concern; you usually do not need to write both.

Follow-up questions

Think of your answer first, then open the hint.

When should you convert?
Show hint
When depth could exceed about 1000 in CPython, or when you need to pause and resume the walk.
Can every recursion be converted?
Show hint
Yes; at worst you simulate frames with a stack of states.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.