Stack & Heap

Task: Watch what survives when a function returns

Why Do We Need Stack and Heap?

In the previous chapter, we learned that a running program needs memory to store the data it works with.

But memory is not used as one undivided space.

Programs organize memory into different regions, each designed for a different purpose.

Two of the most important regions are:

Stack
Heap

Understanding them helps explain questions such as:

Where are local variables stored?
What happens when a function is called?
Why does recursion use the stack?
Where are dynamically created objects stored?
Why can a program run out of stack space?
Why does memory sometimes need to be managed automatically?

You do not need to understand operating-system internals to use the stack and heap.

You need a clear mental model of what they are used for and how their lifetimes differ.

The Big Picture

Think of a running program as having different areas of memory:

For this chapter, focus on two:

Code

Stack → function calls and their local dataHeap  → dynamically allocated data

This is a simplified model. The exact memory layout depends on the programming language, compiler, runtime, and operating system. But this model is extremely useful when learning programming and DSA.

What Is the Stack?

The stack is a region of memory used to manage function calls and their associated data.

When a function is called, the program creates a stack frame for that call. When the function finishes, that frame is removed.

Consider:

Code

void greet() {    int age = 25;}

When greet() runs, the program needs space for information associated with that function call.

Code

Stack                      Stack ┌─────────────────┐        ┌─────────────────┐│ greet() frame   │        │                 ││ age = 25        │        │                 │└─────────────────┘        └─────────────────┘    while it runs            after it finishes

The function's stack frame is no longer needed.

Stack Frames

A stack frame is the memory associated with one active function call.

It can contain information such as:

local variables
function parameters
return information
other execution-related data

Consider:

Code

void add(int a, int b) {    int result = a + b;} add(10, 20);

When add() is called, conceptually:

Code

Stack ┌─────────────────────┐│ add()               ││ a = 10              ││ b = 20              ││ result = 30         │└─────────────────────┘

When the function returns, its frame is removed.

This is why the stack naturally follows the last-in, first-out (LIFO) principle.

Why Is It Called a Stack?

Imagine a stack of books. You place one book on top:

Code

┌─────┐│  C  │├─────┤│  B  │├─────┤│  A  │└─────┘

To remove a book, you take the top one first.

The stack used by a program follows the same basic idea. If A starts, then B, then C, the most recently created frame belongs to C. When C finishes, B continues; when B finishes, A continues.

This is why nested function calls naturally fit the stack.

Function Calls and the Stack

Consider:

Code

void first() {    second();} void second() {    third();} void third() {    int x = 10;}

As each call begins, its frame goes on top:

Code

┌───────────┐   ┌───────────┐   ┌───────────┐│ first()   │   │ second()  │   │ third()   │└───────────┘   ├───────────┤   ├───────────┤                │ first()   │   │ second()  │                └───────────┘   ├───────────┤                                │ first()   │                                └───────────┘

When third() finishes, its frame disappears first, then second(), then first().

This is the fundamental reason function calls are managed using a stack.

Recursion and the Stack

This becomes especially important with recursion.

Code

void count(int n) {    if (n == 0) return;     System.out.println(n);    count(n - 1);}

Calling count(3) creates a sequence of function calls, and each call needs its own stack frame:

Code

count(3) → count(2) → count(1) → count(0) Stack ┌───────────┐│ count(0)  │├───────────┤│ count(1)  │├───────────┤│ count(2)  │├───────────┤│ count(3)  │└───────────┘

Once the base case is reached, the calls return one by one and the frames are removed.

This is why recursion consumes stack memory.

Stack Overflow

The stack has a limited amount of space, and it is far smaller than most people expect. A typical thread gets somewhere around 1 MB of stack, while the heap of the same program can run to gigabytes. Those are typical figures rather than guarantees - the exact size is set by the runtime and the operating system, and can usually be configured - but the ratio is the part worth carrying: roughly a thousand to one.

That is why simple recursion runs out somewhere in the thousands to tens of thousands of frames, not the millions. If a program creates too many nested calls, the stack becomes full. This is called a stack overflow.

Code

void forever() {    forever();}

There is no stopping condition. The calls keep accumulating until the available stack space is exhausted, and the program fails. In Java you will see this:

Code

Exception in thread "main" java.lang.StackOverflowError    at Main.forever(Main.java:3)    at Main.forever(Main.java:3)    at Main.forever(Main.java:3)    ... thousands more, all the same line

The same line repeated down the whole trace is the signature. When you see it, you are looking at a recursion that never reached its base case.

The standard remedy is to rewrite the recursion as a loop, keeping the pending work in an explicit stack you allocate yourself. That data structure lives on the heap, which has room to spare, so the depth limit effectively disappears. It is a common interview follow-up to "what causes a stack overflow?"

Recursion is not automatically bad.

The problem occurs when the number of active calls becomes too large for the available stack space.

What Is the Heap?

The heap is a region of memory used for dynamically allocated data whose lifetime is not tied directly to a single function call.

Objects and other dynamically created data are commonly stored in the heap.

For example:

Code

Student student = new Student();

The variable student is associated with the current function's execution, while the object created with new lives in dynamically allocated memory.

The exact details depend on the language and runtime, but this distinction is extremely useful.

Why Do We Need the Heap?

Imagine a function creates an object that needs to continue existing beyond the function's local execution.

A function's stack frame disappears when the function returns. So data that needs a longer or independently managed lifetime cannot simply depend on that frame.

The heap provides memory for dynamically allocated data.

Code

Student createStudent() {    Student s = new Student();    return s;}

The object can continue to exist even though the function that created it has finished. The animation above walks through exactly this: the frame appears, allocates, returns and is removed, and the object stays where it was.

Stack vs Heap

The simplest comparison is:

Stack	Heap
Manages function calls	Stores dynamically allocated data
Uses stack frames	Uses dynamically allocated memory
Naturally follows LIFO	Does not follow LIFO
Local execution data is commonly stored here	Objects and dynamic data are commonly stored here
Frames are removed when calls return	Data remains until it is no longer needed and reclaimed
Usually faster to allocate and release	Generally more flexible
Limited in size	Usually much larger

One important point: "Stack is fast and heap is slow" is an oversimplification. The actual performance depends on the language, runtime, allocation strategy, hardware, and access pattern.

The more useful distinction is:

The stack is organized around function execution; the heap is organized around dynamically allocated data and its lifetime.

A Function Using Both

Consider:

Code

void process() {    int count = 10;    Student student = new Student();}

A simplified mental model is:

Code

Stack ┌─────────────────────┐│ process()           ││ count = 10          ││ student ────────────┼──────┐└─────────────────────┘      │                             ↓Heap                    ┌──────────────┐                        │ Student      │                        │ object       │                        └──────────────┘

The function call and its local execution data are associated with the stack. The dynamically created object is associated with the heap.

This distinction becomes particularly useful when we study references and pointers.

Who Cleans Up the Heap?

This depends on the programming language.

Some languages require programmers to explicitly manage dynamically allocated memory. For example, in C++:

Code

Student* s = new Student(); delete s;

The programmer is responsible for releasing the allocated memory.

Languages such as Java and Python use garbage collection to automatically reclaim heap memory that is no longer reachable by the program.

Code

Object is no longer reachable             ↓      Garbage collector             ↓       Memory reclaimed

This does not mean garbage-collected languages never have memory problems. A program can still keep unnecessary objects reachable and consume excessive memory.

Stack and Heap in Different Languages

The stack/heap model is useful across many languages, but the exact implementation differs.

C / C++ give programmers more direct control over memory allocation.

Code

int x = 10;int* p = new int(20); delete p;

Java allocates objects created with new on the heap in the usual conceptual model, while local variables and references are associated with stack frames. Java's garbage collector manages heap memory.

Python is more abstract. Objects are managed by the Python runtime, and implementation details such as CPython's memory management do not map perfectly onto the simple "everything is either stack or heap" model.

So do not assume that every language follows the simplified model identically.

Common Misconceptions

"Every local variable is always stored on the stack." Not necessarily. Compilers keep values in registers, and some runtimes place an object on the stack when they can prove nothing outside the function will ever see it.

"Heap memory is infinite." No. It is larger, not unlimited. Allocate enough and the program fails the same way, with an out-of-memory error rather than a stack overflow.

"Garbage collection deletes an object the moment it stops being used." No. The runtime reclaims it when it next chooses to look, which may be a long time after the last reference disappeared.

Stack vs Heap: The Mental Model

If you remember only one picture from this chapter, remember this:

Code

                Running Program                      │          ┌───────────┴───────────┐          ↓                       ↓       STACK                    HEAP          │                       │   Function calls          Dynamic data   Stack frames            Objects   Local execution         Longer-lived data   parameters              Dynamic allocation

The stack answers:

"What is currently happening in my function calls?"

The heap answers:

"Where can dynamically allocated data live independently of a particular function call?"

This mental model will be enough for most of the DSA you will study.

Quick Check

What is a stack frame?
Why are function calls naturally managed using a stack?
Why does recursion consume stack memory?
What causes a stack overflow?
What is the heap used for?
Why can an object outlive the function that created it?
What is the main conceptual difference between stack and heap?
Does every programming language implement stack and heap exactly the same way?

Show answer

The block of memory a single function call gets for its parameters, its local variables and the address it must return to. One call, one frame.
Because calls always finish in the reverse order they started. The function you called most recently is always the one that finishes next, which is exactly last-in first-out.
Because every active call needs its own frame, and in a recursion none of them have returned yet. A recursion n deep holds n frames at once.
Nesting calls deeper than the stack has room for, which in practice almost always means a recursion that never reaches its base case. The stack is around 1 MB, so the limit arrives in the thousands of frames.
Data whose lifetime is not tied to a single call: anything that must outlive the function that created it, or whose size is not known until the program runs.
Because the object is not in the frame. The frame holds a reference to it, and when the frame is removed only the reference goes. The object stays in the heap for as long as something still points at it.
The stack is organised around function execution and cleans itself up automatically in LIFO order. The heap is organised around lifetime, and something has to decide when its data is finished with.
No. The stack and heap are a model, not a specification. Languages, compilers and runtimes differ in what goes where, and some have no heap at all in the usual sense.

Quick Recap

The stack manages active function calls.
Each function call gets a stack frame.
Stack frames are removed when their function calls return.
Recursion creates multiple active stack frames.
Too many active calls can cause a stack overflow.
The heap provides memory for dynamically allocated data.
Heap data can have a lifetime independent of a particular function call.
Memory management differs between languages.
Garbage-collected languages automatically reclaim unreachable heap objects.
Stack and heap are useful mental models, but actual implementations can be more complex.

Where This Leads

We now know:

Code

Memory   ↓Stack & Heap   ↓Different places for different kinds of data

But one important question remains:

How does one piece of data refer to another location in memory?

That is where pointers and references come in. They are the mechanism behind many of the structures you will soon encounter: linked lists, trees, graphs and hash tables.

Understanding them will make those data structures much easier to visualize.

The stack organizes memory around active function calls, while the heap provides memory for dynamically allocated data. The difference between their organization and lifetime is fundamental to understanding recursion, objects, references, and many data structures.