Question

Which data structure is used by the system to implement recursion?

• A. Queue
• B. Stack
• C. Linked List
• D. Heap

Hint:

Recursion internally uses the {call stack}. Each recursive call adds a new stack frame, and when the base case is reached, frames are removed in reverse order.

Answer 1

The Correct Option is B

Concept: Recursion occurs when a function calls itself during execution. To manage multiple function calls, the system uses a call stack. A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Each function call creates a new activation record (stack frame) that is pushed onto the stack.
Step 1: Understand how recursion works.
When a recursive function is called, the system:

• Stores the current function state (parameters, return address, local variables).
• Pushes this information onto the stack as a stack frame.

Step 2: Function calls and stack behavior.
Each recursive call is placed on top of the stack. When the base case is reached, the stack begins to unwind and function calls are removed in reverse order. Example: \[ \text{factorial}(3) \rightarrow \text{factorial}(2) \rightarrow \text{factorial}(1) \] Stack behavior: \[ \text{Push } f(3) \rightarrow f(2) \rightarrow f(1) \] Then they are popped in reverse order.
Step 3: Conclusion.
Since recursion requires storing and retrieving function calls in Last In First Out order, the system uses a: \[ \text{Stack} \]