A girl and a robot thinking together

Think it through together · A little story

A girl stacks task cards marked “not finished yet.” The card on top shows what the robot is working on right now.

Lay out the process

Follow the numbered steps, then explain them in your own words
  1. main waitsSave its return point
  2. A waitsA calls B
  3. B finishesRemove B’s card
  4. A continuesThen return to main

The call stack helps manage the return order of ordinary function calls.

The most recently entered call finishes and returns first, like taking the top task card. A card can also record information the current call needs to keep.

See calls and returns in action

The task cards go from left to right, from the bottom of the stack to the top. The rightmost card represents the call that is currently running.

Step 1 · Enter factorial(3)
f(3)

This call needs to calculate 3 × f(2), so it waits for f(2).

Step 2 · Enter factorial(2)
f(3) waitingf(2)

This call needs to calculate 2 × f(1), so another level is added.

Step 3 · Continue to the base case
f(3) waitingf(2) waitingf(1) waitingf(0) = 1

f(0) returns 1 directly, so no more calls are added.

Step 4 · Return to factorial(1)
f(3) waitingf(2) waitingf(1) = 1

Calculate 1 × 1 to get 1, then return.

Step 5 · Return to factorial(2)
f(3) waitingf(2) = 2

Calculate 2 × 1 to get 2, then return.

Step 6 · Return to factorial(3)
f(3) = 6

Calculate 3 × 2 to get 6. This call is complete.

01Why remember “who called whom”?

If main calls A, and A calls B, the program must remember:

  • Where to return in A after B finishes
  • Where to return in main after A finishes

02How can we picture a call stack?

For now, picture a stack of plates: the plate put on last must be taken off first.

B()A()main()

This last-in, first-out (LIFO) relationship is a natural way to represent nested function calls.

03What does one call put on the stack?

A common implementation maintains a stack frame or similar call state for each active function call. It may contain:

Return information

Where execution should continue after the function ends.

Local data

Some local variables.

Saved registers

Information for restoring the caller’s state.

Argument-related data

Depending on the calling convention.

04What changes when A calls B?

Step 1

main

→
Step 2

A
main

→
Step 3

B
A
main

When B returns, its call state is removed first and execution goes back to A. When A returns, execution goes back to main.

05Why is it called a “stack”?

The order in which active calls are added and return usually follows this rule:

The function called last returns first

This is the defining feature of the stack data structure.

06Does the C++ standard require a physical stack like this?

No. It does not require every function to be implemented using one fixed “physical stack frame” layout.

A compiler may inline a function or optimize local data and registers.

07What happens if calls go too deep?

As active calls keep increasing, the amount of runtime call state needed also increases.

Real systems have limited stack space, and calls that go too deep may cause a stack overflow.

This will matter a lot when we study recursion in the next topic.

What you have learned

  • The call stack helps a program keep track of nested function calls.
  • A function called later usually returns earlier, following last-in, first-out order.
  • Common implementations maintain a stack frame or equivalent state for active calls.
  • A stack frame may contain return information, local data, and registers.
  • The C++ standard does not prescribe one fixed stack-frame layout.
  • Calls that go too deep may use up the available stack space.

Next: How do you break a big problem into several functions?

Your turn to try

main calls A, and A calls B. When B finishes, does execution return to main or to A first?

Have you thought it through? Open for an explanation

It returns to A first. After A finishes, execution returns to main. The most recently entered call returns first.