Push a frame on a call
Updated
Entering a function pushes a frame: the current n (or node, or index) plus where to resume. The previous frame is still there, frozen. You do not overwrite it.
What to focus on
In an explicit stack, push({n, phase}). In language recursion the compiler does this. Two calls in a row (DFS left then right) push the second on top of the first's leftover.
Worked examples
one call
a = [], call f(4)- push frame n=4
Result: stack [f(4)]
nested
a = [f(4)], call f(1)- push f(1)
- f(4) buried
Result: [f(4), f(1)]
sibling leftover
a = [f(4), f(left)], return left, call f(right)- parent f(4) never left
- push f(right)
Result: [f(4), f(right)]
Try it
Write pushFrame(stack, n). stack is the call stack of frames. n is the argument of the new call. Push a new frame. Do not overwrite the parent. Print the stack. a = [], call f(4) → stack [f(4)]. a = [f(4)], call f(1) → [f(4), f(1)]. a = [f(4), f(left)], return left, call f(right) → [f(4), f(right)].
You may push onto an empty call stack. Frames are well-nested calls.