GATE CS 2010 Q14 — Runtime Environments

To determine which language feature necessarily requires heap allocation, let's analyze the runtime memory requirements for each option:

• Option A (Recursion): Recursion requires a stack-based runtime environment. Each recursive call creates a new activation record (stack frame) on the call stack to store local variables and return addresses. A heap is not required for recursion.
• Option B (Dynamic Scoping): Dynamic scoping can be implemented efficiently using a stack (e.g., using a central symbol table or an association list on the activation stack). It does not require a heap.
• Option C (Dynamic Data Structures): Dynamic data structures (such as linked lists, trees, and graphs) can grow or shrink arbitrarily during execution. Furthermore, their lifetime is often independent of the scope or function that created them (e.g., a node created inside a function can persist after the function returns). Therefore, they necessarily require heap allocation for dynamic memory management.
• Option D (Global Variables): Global variables have a lifetime that spans the entire execution of the program. They are allocated in a fixed, static data area at compile-time, not on the heap.

Thus, languages that allow dynamic data structures necessarily need heap allocation in the runtime environment.