Skip to content
GATETECH
Official PYQ · 1994Q21RecursionNAT1 mark

GATE CS 1994 Q21 — Recursion

Explain with AI

Consider the following recursive function:

function fib (n:integer);integer;
begin
if (n=0) or (n=1) then fib := 1
else fib := fib(n-1) + fib(n-2)
end;

The above function is run on a computer with a stack of 6464 bytes. Assuming that only return address and parameter are passed on the stack, and that an integer value and an address takes 22 bytes each, estimate the maximum value of nn for which the stack will not overflow. Give reasons for your answer.

View worked solution

Answer: 16

To find the maximum value of nn for which the stack does not overflow, we first determine the size of a single stack frame and the maximum recursion depth.

  1. Stack Frame Size: Each stack frame stores the parameter (an integer) and the return address (an address).
    Frame Size=2 bytes (parameter)+2 bytes (return address)=4 bytes\text{Frame Size} = 2\text{ bytes (parameter)} + 2\text{ bytes (return address)} = 4\text{ bytes}
  2. Maximum Recursion Depth: The longest chain of active recursive calls occurs along the left-most path of the recursion tree: fib(n)→fib(n−1)→fib(n−2)→⋯→fib(1)\text{fib}(n) \to \text{fib}(n-1) \to \text{fib}(n-2) \to \dots \to \text{fib}(1) The maximum number of active stack frames at any point during this execution is nn.

For a stack of 6464 bytes, the condition to avoid overflow is:

n×4≤64  ⟹  n≤16n \times 4 \le 64 \implies n \le 16

Thus, the maximum value of nn for which the stack will not overflow is 16.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Recursion questions