Static vs stack vs heap allocation: which language features force which

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Under call by reference, what does the callee receive? from Lesson 5.4
• What is in an activation record? from Lesson 5.2
• What is the difference between compile time and run time? from Lesson 0.1.1

1 · The Story

📖

Three policies

Rhea has tried three ways of running the Records Room.

In the old days she gave every speaker one fixed drawer, labelled before the evening. Simple and fast, but if a speaker was interrupted and had to speak again inside their own turn, both turns fought over the same drawer.

Then the tray pile: a new tray for every turn, removed at the end of the turn. Interrupting yourself is fine. But if a speaker hands the audience a page from their tray and then leaves, that page is gone; anyone who later looks for it finds an empty spot, or someone else’s notes.

So for anything that must outlive a turn, she uses the lost-and-found: it stays until somebody explicitly throws it out, or until her assistant does a round to collect items nobody can reach any more.

2 · Predict First

🤔

Can a language without recursion and without dynamic data structures give every variable a fixed address before the program runs? Write your guess down. The answer is in the vault.

3 · Core Concept

Static allocation

Every name gets a fixed address at compile time, for the whole run. Requirements: sizes known at compile time; no recursion (at most one activation per procedure at a time); no data created at run time. Locals keep their values between calls. Example: Fortran 77.

Stack allocation

Activation records are pushed on call and popped on return. Needed as soon as there is recursion (several activations of one procedure at once). Locals live exactly as long as their call. A local array whose size is known only at run time can still go on the stack (its size is fixed when the call starts). Example: C, Pascal locals.

Heap allocation

Memory is allocated and freed in any order. Needed when data must outlive the call that created it or its amount is unpredictable: malloc/new, linked structures, objects, closures (functions that capture local variables and are returned or stored), and languages where activations can outlive their callers.

Dangling references and garbage

• A dangling reference is a reference to storage that has been deallocated: returning the address of a local variable (its record is popped), or using heap memory after free.
• Garbage is allocated storage that can no longer be reached. Garbage collection finds unreachable heap objects and reclaims them (reference counting, or mark-and-sweep from the roots: globals, stack, registers).

Which feature forces which

Story → compiler term

4 · Visual

int *bad() {              /* dangling reference */
    int x = 5;
    return &x;            /* x's record is popped at return */
}
int *good() {
    int *p = malloc(sizeof(int));
    *p = 5;
    return p;             /* heap memory outlives the call */
}

Each strategy supports more language features than the one before.

5 · Worked Examples

Example 1 Easy

Which allocation does each need: (a) Fortran 77 programs; (b) a recursive factorial in C; (c) building a linked list whose length is read from input?

Solution

(a) static; (b) stack; (c) heap. Rhea’s three policies.

Example 2 Medium

Why is bad() above wrong, and how does good() fix it?

Solution

bad returns the address of x, which lives in bad’s activation record; the record is popped at return, so the pointer dangles (the page from a removed tray). good allocates on the heap, which is not tied to the call.

Example 3 GATE

A language has recursion but no pointers and no dynamic data. A second language has no recursion but allows functions to be returned as values that use the locals of the function that created them. Which allocation does each need?

Solution

The first needs stack allocation (recursion), and no heap. The second needs heap allocation for the captured locals, because they must outlive the creating call; without recursion a stack is not required for the rest.

6 · Shortcuts

⚡

Feature → strategy: recursion → stack; outlives the call → heap; neither → static suffices. Valid when: MCQs pairing features with allocation strategies.

⚡

Dangling check: does a pointer survive longer than what it points to? Then it dangles. Valid when: questions with returned addresses or freed memory.

7 · GATE Traps

⚠️

• Static allocation cannot support recursion: two activations would share one set of locals.
• Variable-size local arrays do not require the heap if their size is fixed when the call starts.
• Returning a pointer to a local variable is a dangling reference, not a compile-time error in C.
• Garbage collection reclaims unreachable heap objects; it does not touch the stack.
• Static locals in C keep their value between calls because they are statically allocated.

8 · Memory Hook

🧠

Drawer, tray, lost-and-found. Recursion needs trays; long-lived data needs lost-and-found.

9 · Connect the Dots

Phase 5 is complete: you know where every value lives while the program runs. Phase 6 returns to the draft code and makes it faster, starting inside single basic blocks.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markFeatures

A language with recursion requires at least:

• (A) static allocation
• (B) stack allocation
• (C) heap allocation
• (D) garbage collection

Q2MCQ1 markDangling

Returning the address of a local variable from a C function creates:

• (A) a memory leak
• (B) a dangling reference
• (C) a static variable
• (D) a heap object

Q3MSQ1 markStatic allocation

Which are requirements for using static allocation alone?

• (A) no recursion
• (B) sizes known at compile time
• (C) no data created at run time
• (D) only global variables

Q4MCQ1 markHeap

Which feature forces heap allocation?

• (A) global constants
• (B) recursion
• (C) objects that must outlive the procedure that created them
• (D) local integer variables

Q5MCQ1 markGarbage collection

Garbage collection reclaims:

• (A) stack records after return
• (B) heap objects that can no longer be reached
• (C) static data
• (D) code

11 · Rule Card

• Static: fixed addresses; needs no recursion, known sizes, no run-time data.
• Stack: supports recursion; lifetimes nested (LIFO).
• Heap: lifetimes beyond calls (malloc/new, objects, returned closures).
• Dangling reference: pointer outlives its target (address of a local, use after free).
• Garbage collection: reclaim unreachable heap objects (reference counting, mark-and-sweep).

12 · Concept Ledger

static allocationstack allocationheap allocationdangling referencegarbagegarbage collectionclosure (brief)

13 · Answer Vault