The Call Stack and Stack Frames

Any active function call requires one block of memory of size a stack frame. The frames are stacked one above the other in an area in the memory called the call stack.

The top frame belongs to the function that's currently executing. The frames below it belong to the functions who are waiting for the current call to return.

A stack frame can be viewed as the information the function needs while it runs. At a minimum, this is the return address, space for any parameters, and space for any local variables.

The return address specifies to the machine where to proceed to after the function execution completes.

There are other mechanisms, also, for saving away registers that the function might change. Quite simply, the idea is the same: each function call gets its own private region of memory that is exclusive to its lifetime.

Execution starts in main. As soon as main calls some other function, a new frame is pushed into the call stack.

The frame has a return address to main, a place to keep the parameters for the function, and a place to keep the local variables.

If this function transmits to a second level, then another frame is added on top of the previous one.

#include <iostream>

void inner(int x)
{
    int local{x * 2};
    std::cout << "inner sees local = " << local << '\n';
}

void middle(int y)
{
    int temp{y + 1};
    inner(temp);
    std::cout << "middle sees temp = " << temp << '\n';
}

int main()
{
    middle(10);
}

There could be multiple stack frames alive when the innermost function is executing. The frame of main stays at the bottom, a frame for the function called from main is above it, and the execution of the innermost function occurs in a frame at the top.

The active function's frame is popped from the stack when the closing brace of the active function has been reached or the active function is executing a return.

The local variables are gone, and execution will jump to the return address stored for that call.

Now, the top frame is once again the called frame. Remember that its local variables are still accessible as its frame hasn't been popped yet.

Once the caller has finished, its frame is popped and execution is returned to the function below.

This is why an auto local variable will disappear after the function it was created in no longer exists.

Their storage is part of the function's stack frame. After the frame is popped, they are no longer allocated to those names.

So any effort to access a local after its function has returned is pointless, that data no longer lives inside a valid frame.

It's particularly clear how recursion causes the call stack to grow:

Each recursive call adds a new frame with a copy of the parameters and local variables.

The frames go on adding and upon return of base case, they go on popping back in reverse order.

A recursive call using 4 in call to foo might call the same function with 3. That call creates a new frame and calls the function with 2.

And so, Recursion.

#include <iostream>

int sum_down(int n)
{
    if (n <= 0)
    {
        return 0;
    }

    return n + sum_down(n - 1);
}

int main()
{
    std::cout << "sum is " << sum_down(4) << '\n';
}

Notice that the deepest call will return first. The function above it will receive the return value of the deepest call and then it will calculate with it, and finally return it. This process continues until the original call is returned with the value.

Each frame holds its own values of parameters. The effect of changing a value in one recursive call does not take effect on values held in other frames.

The call stack has a fixed size.

An unbounded chain of calls will eventually fill the stack.

An example reason is a recursive function with no end condition. This keeps adding a new frame until the environment runs out of stack space and kills the program.

Even a well designed recursive function can overflow the stack if the recursion becomes too deep.

The maximum practicable depth is dependent on the environment, and how much storage a frame takes. This is not a rule in the C++ language.

The call stack, but I will also not hide the fact that the call stack has traditionally been thought of as a stack, which it is not.

Is a storage mechanism that automatically pushes and pops private data for each invocation.

It is also a cache of incomplete tasks that indicates to the computer where to resume execution after each return.

Frames are pushed when functions are called, and popped when functions return.

This ensures that the data for one invocation does not intermix with data for any other active invocation.

When a function is done, its frame is released and its private storage is gone.

#include <iostream>

void inner(int x)
{
    int local{x * 2};
    std::cout << "inner sees local = " << local << '\n';
}

void middle(int y)
{
    int temp{y + 1};
    inner(temp);
    std::cout << "middle sees temp = " << temp << '\n';
}

int main()
{
    middle(10);
}

#include <iostream>

void inner(int x)
{
    int local{x * 2};
    std::cout << "inner sees local = " << local << '\n';
}

void middle(int y)
{
    int temp{y + 1};
    inner(temp);
    std::cout << "middle sees temp = " << temp << '\n';
}

int main()
{
    middle(10);
    middle(3);
}

inner sees local = 22
middle sees temp = 11
inner sees local = 8
middle sees temp = 4