GATE CS Mastery
Cheat sheets

GATE CS 2014 Set 3 · Compiler Design

Question 28

MCQPrinted as CS Q.181 markWrong answer: −1/3Medium (estimate)

Question

Which of the following statements are CORRECT?

  1. Static allocation of all data areas by a compiler makes it impossible to implement recursion.
  2. Automatic garbage collection is essential to implement recursion.
  3. Dynamic allocation of activation records is essential to implement recursion.
  4. Both heap and stack are essential to implement recursion.
Choose one option
Official answer and solution
Official answer
D
From
Official GATE 2014 answer key

Solution

Evaluate how runtime memory allocation strategies (static vs. dynamic activation records) affect support for recursion.

  1. Statement 1 (CORRECT):
    In a static allocation scheme (used in early languages like Fortran 77), a compiler assigns a single fixed memory location for the local variables, parameters, and return address of each procedure. When a recursive call is made, the new invocation would overwrite the values belonging to the currently active invocation. Thus, static allocation makes recursion impossible.

  2. Statement 2 (INCORRECT):
    Recursion creates and destroys activation records in a last-in, first-out (LIFO) order. Deallocation occurs deterministically when a function returns by popping the activation record off the call stack. Automatic garbage collection is needed for dynamically allocated heap memory with unpredictable lifetimes, not for stack-based activation records.

  3. Statement 3 (CORRECT):
    Because multiple instances of a recursive function must coexist simultaneously with distinct copies of local variables and parameters, activation records must be allocated dynamically at runtime as calls occur (typically on a call stack).

  4. Statement 4 (INCORRECT):
    Recursion requires a stack for activation records; heap storage is not required to implement recursive function calls.

Therefore, only statements 1 and 3 are correct (option D).

Final answer

D

Common trap

Believing garbage collection is needed for recursion, confusing heap reclamation with deterministic call stack management.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2014 Computer Science and Information Technology (CS) Session 3
Question
28 of 65, printed as CS Q.18
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.