Foundations
Memory Models
Difficulty: Intermediate
Why does a deeply recursive function crash with a stack overflow while an equivalent loop happily processes a million elements? Why does passing an array into a function sometimes mutate the caller's data and sometimes not? The answers...
Memory Models
Why does a deeply recursive function crash with a stack overflow while an equivalent loop happily processes a million elements? Why does passing an array into a function sometimes mutate the caller's data and sometimes not? The answers all live one level below your code, in the runtime memory model that decides where every variable, object, and function call physically lives.
This lesson opens up that model. You will see the difference between the stack (small, fast, organized into per-call frames) and the heap (larger, manually or garbage-collected, where objects and arrays actually live), watch how every function call pushes a stack frame and every return pops one, and trace how recursion stacks frames on top of frames until the base case unwinds them. You will also meet references and pointers conceptually, learn what triggers a stack overflow, and get a working mental model of garbage collection and memory leaks.
This lesson builds on Space Complexity Fundamentals, where you learned to count auxiliary versus total space and saw why some algorithms claim O(1) space while others need O(n). Memory Models gives you the underlying picture: those O(...) numbers describe stack frames, heap allocations, and reference graphs that you can now visualize concretely.
Next, you will pivot to the mathematical side of the foundations track with Discrete Mathematics Basics, picking up the sets, relations, and logic vocabulary that algorithm analysis depends on.
Prerequisites:
Space Complexity FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Distinguish between stack memory and heap memory and explain what is stored in each.
Trace the call stack as functions are called and returned, identifying each stack frame.
Explain how recursive calls consume stack space and calculate the stack depth for a given recursion.
Define references and pointers conceptually and explain how they differ from value copies.
Identify conditions that cause stack overflow and describe strategies to avoid it.
Explain garbage collection and memory leaks at a conceptual level.
Why This Matters
01
Space complexity analysis requires understanding where variables live in memory and how much space each function call consumes.
02
Recursion creates a new stack frame for every call, which is why deep recursion can crash a program with a stack overflow error.
03
Interviews frequently ask about the call stack, especially when tracing recursive algorithms or debugging stack overflow errors.
04
Understanding references vs values is critical for predicting whether a function modifies its input or works on a copy.
Key Terms
8 terms you'll encounter in this lesson
Stack memory
A region of memory that stores function call frames in LIFO order. Each frame holds local variables, parameters, and the return address. Memory is automatically freed when a function returns.
Heap memory
A region of memory used for dynamically allocated data (objects, arrays, strings). Unlike the stack, heap memory is not freed automatically and must be managed by the programmer or garbage collector.
Stack frame
A block of memory on the call stack created each time a function is called. It contains the function's parameters, local variables, and metadata about where to return.
Call stack
The data structure that tracks which functions are currently executing. Each function call pushes a frame; each return pops a frame. Follows LIFO order.
Stack overflow
An error that occurs when the call stack exceeds its maximum size, typically caused by infinite or very deep recursion.
Garbage collection
An automatic memory management process (used in JavaScript, Python, Java) that identifies and frees heap memory that is no longer reachable by any variable.
Reference
A variable that stores the memory address of an object rather than the object itself. Multiple references can point to the same object in heap memory.
Memory leak
A situation where allocated heap memory is no longer needed but cannot be freed because references to it still exist, causing the program to use increasing amounts of memory over time.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"The stack and the heap are the same thing"
The stack and heap are separate memory regions with different purposes. The stack is for function call frames (automatic, LIFO). The heap is for dynamically allocated objects (manual or garbage-collected). They grow toward each other in memory but serve very different roles.
"Recursion uses no extra memory because you are calling the same function"
Each recursive call creates a NEW stack frame with its own copy of parameters and local variables. A function that recurses n times uses O(n) stack space, even though it is the 'same' function.
"Garbage collection prevents all memory leaks"
Garbage collection only frees memory that has no remaining references. If you accidentally keep a reference to a large object (e.g., in a global array or closure), the GC cannot free it. This is a memory leak even in garbage-collected languages.
"Stack overflow means you ran out of all system memory"
Stack overflow specifically means the call stack exceeded its fixed size limit (typically 1-8 MB). Your system may still have gigabytes of free heap memory. The stack is intentionally small to catch infinite recursion quickly.