The call stack is a stack

Calls nest

When function A calls function B, A stops in the middle of what it was doing, B runs to completion, and then A carries on from exactly where it stopped. If B calls C, C finishes before B does, and B before A. The most recent call always finishes first. That is the LIFO rule, so the natural way to keep track of unfinished calls is a stack.

Every running thread has one, called the call stack. Each call pushes a stack frame onto it, and each return pops it off. The details of a frame are the subject of the next module's first lesson, but the essentials are:

• the return address, the instruction in the caller to continue from;
• the function's arguments, or space to save them;
• its local variables;
• copies of registers the function will overwrite and must restore.

Pushing and popping frames

The trace above follows f(3), a recursive factorial. main calls f(3), which pushes a frame holding n = 3. f(3) calls f(2), which pushes another frame with its own n = 2: each call has its own copy of its locals, which is why recursion works at all. f(2) calls f(1), and the stack reaches its deepest point.

f(1) returns 1 without calling anything. That pops its frame, and the frame now on top is f(2)'s, so f(2) resumes, computes 2 × 1 and returns. Then f(3) resumes, computes 3 × 2 and returns 6 to main. The frames come off in the exact reverse of the order they went on.

Pushing and popping are as cheap as on any array-based stack. The processor keeps the address of the top in a register, the stack pointer. A call moves it down by the frame's size, one subtraction; a return moves it back. No allocator is involved, which is why local variables cost almost nothing to create, and why they disappear the moment a function returns.

Stack overflow

The call stack is a fixed region of memory reserved for each thread. Typical sizes are 8 MB for the main thread on Linux, 1 MB on Windows, and 512 KB for additional threads on macOS. A frame is usually somewhere between tens and hundreds of bytes, so the stack holds thousands to tens of thousands of frames.

Recursion that goes deeper than that overflows the stack: the next push would run into memory that isn't part of it. In C or C++ this is a crash, typically a segmentation fault. Java throws StackOverflowError, JavaScript throws "Maximum call stack size exceeded", and Python refuses well before the real limit with a RecursionError at a default depth of 1,000, which sys.setrecursionlimit can raise.

So recursion depth is a resource, just like memory. A recursive function whose depth grows with n uses O(n) stack space, and that matters whenever n can be large: walking a linked list of a million nodes recursively, or a tree that has degenerated into a long chain. Some languages, such as Scheme, guarantee that a call in tail position reuses the current frame, so certain recursions run in constant stack space. Python, Java and JavaScript (in practice) don't, so you can't rely on it there.

An explicit stack instead

Anything recursion does with the call stack, a loop can do with a stack of its own. The explicit stack holds the same unfinished work that the frames would have held, but it lives in heap memory, which can grow to gigabytes.

Here is a recursive walk over a tree, and the same walk with an explicit stack:

def total(node):                     # recursive
    if node is None:
        return 0
    return node.val + sum(total(c) for c in node.children)
 
def total_iterative(root):           # explicit stack
    result, stack = 0, [root]
    while stack:
        node = stack.pop()
        if node is not None:
            result += node.val
            stack.extend(node.children)
    return result

The iterative version pushes children instead of calling itself on them, and pops a node instead of returning to it. It visits the nodes in a different order, which doesn't matter for a sum. When order does matter, or when work has to happen after the children finish, the explicit stack has to remember more, such as which child to visit next. The trees and graphs modules show those versions.

The trade-off is readability. Recursion states many algorithms more clearly, and for trees that stay shallow, such as balanced search trees, which stay a few dozen levels deep even with a trillion keys, it is perfectly safe. Use an explicit stack when the depth depends on the input and could be large.

Reading a stack trace

When a program crashes, it usually prints a stack trace: the list of frames that were on the call stack at that moment, from the innermost call outward. Each line names a function and the line it was executing, which is the return address made readable. Read it from the line where the error happened back toward main, and you are reading the chain of calls that led there. A stack overflow produces a distinctive trace: the same function, or a small cycle of functions, repeated thousands of times. Debuggers show the same list live, and let you inspect each frame's local variables, because each frame really does hold its own copy of them.

The bigger picture

The call stack completes this module. Stacks handle what is most recent and unfinished; queues handle what has waited longest; deques do both; and every program you run is already using a stack to keep its function calls straight. The Core level starts by looking inside those stack frames, and then uses recursion, deliberately and carefully, as a tool for solving problems.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate The call stack is a stack from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function next_greater_elements(nums):
    n = length(nums)
    ans = array of size n filled with -1
    stack = empty_stack()  // stores indices with decreasing values
    for i from 0 to n - 1:
        while not stack.empty() and nums[stack.top()] < nums[i]:
            idx = stack.pop()
            ans[idx] = nums[i]
        stack.push(i)
    return ans

#include <vector>
 
std::vector<int> nextGreaterElements(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> ans(n, -1), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            ans[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}

import java.util.*;
 
public class StackQueueSolver {
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peekLast()] < nums[i]) {
                ans[st.pollLast()] = nums[i];
            }
            st.offerLast(i);
        }
        return ans;
    }
}

def next_greater_elements(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.