Your Own Call Stack
Recursion: lesson 8 of 8
Not a tail call? Then carry the stack yourself.
Lesson 8 of 8 · 6 min
Your Own Call Stack
Step 1 of 12
No tail call here: work remains after the recursive call, so something has to remember the way back.
The Idea
When work remains after the recursive call, a loop alone cannot replace it — something has to remember where to come back to. So keep that stack yourself.
For an inorder walk: dive left, pushing every node you pass. When the left runs out, pop, report, and turn right. The pushed nodes are the pending frames.
Real-World Example
Exploring a cave system with a pocketful of markers. At every fork you drop a marker and take the left tunnel. Dead end reached, you pick up the last marker and take that fork's right tunnel instead.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def inorder(root):
out, stack, n = [], [], root
while stack or n:
while n: # walk left as far as it goes, noting the way back
stack.append(n); n = n.left
n = stack.pop() # nothing further left, so this node is next
out.append(n.val)
n = n.right # now do the same on its right side
return out
print(inorder(Node(4, Node(2, Node(1), Node(3)), Node(5)))) # [1, 2, 3, 4, 5]Your turn
Put the steps in the right order.
- Pop the top node and append its value to the output
- Move to that node's right child and repeat the whole process
- Start at the root with an empty stack
- Push the current node and step left, until there is no left child
Mini quiz
1 / 3