GATE CSE 1994 | Question: 21

Question

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 $64$ bytes. Assuming that only return address and parameter are passed on the stack, and that an integer value and an address takes $2$ bytes each, estimate the maximum value of $n$ for which the stack will not overflow. Give reasons for your answer.

Comments

The maximum number of activation records live in the stack at any time = The height of the corresponding recursion tree.

 

This is because the recursive calls are popped off of the stack, when they’re finished executing.

$fib(n)$ definitely pushes $O(2^n)$ activation records on the stack in entirety, but only $O(logn)$ activation records are present in the stack at any given time.

---

Here why we are not considering the activation record for main which had called fib. Otherwise program could not have been directly started from function call.

---

ronak.ladhar nothing has been mentioned about the c programming language.

---

ronak.ladhar coz its not given in the question’s pseudo code.

---

If this code is implemented in C language, and suppose the question is same i.e
The C function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter are passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow.

We know that order of evaluation is undefined, and its up to the implementation of the compilers that which function gets evaluated first. 

If a compiler is designed to generate assembly that calls fib(n-2) first then fib(n-1), then n will be 32. 

If fib(n-1) is getting evaluated first, then n will be 16.

@Sachin Mittal 1 sir, from this can we say that max values of n can be 16 or 32 for the above case ?

---

^How you are getting 32 ?

Answer 1

Size of an activation record $= 2 + 2 = 4$ bytes.

So, no. of possible activation records which can be live at a time $= 64/4 = 16$.

So, we can have $16$ function calls live at a time (recursion depth $= 16$), meaning the maximum value for $n$ without stack overflow is $16$ (calls from $1-16$). For $n=17$, stack will overflow.

This is different from the total no. of recursive calls which will be as follows:
$$\begin{array}{|c|c|} \hline \textbf{n} &  \textbf{No. of calls} \\\hline 1 & 1 \\\hline 2 & 3 \\\hline 3 & 5 \\\hline 4 & 9 \\\hline 5 & 15 \\\hline 6 &25 \\\hline \end{array}$$

Comments

@rahul sharma 5 I also have the same doubt as yours, where would they store the computed results if they only have parameters and return address in activation record and how it works.

Please tell me if you get your doubt clear as I am still confused in that part.

---

The longest call chain in the recursion tree should correspond to the maximum calls possible. Each edge in that call chain corresponds to an activation record. 64bytes allows 16 activation records therefore the maximum value of n(vertices) that produces 16 edges is 17(e+1).

---

I’m guessing, that the returned value will be stored in the calling function and then second sub-tree will be computed.

Answer 2

ans is n=5.

size of activation record = 2 + 2 = 4 bytes

size of stack = 64 bytes

so, 64/4 = 16 activation records we can push.

no of activation records = no of recursive calls

and no of recursive calls for Nth fibonacci num is = 2*fib(n+1) - 1

here it should be less than 16, if we take n=5 then no of rec calls are 2*fib(6) - 1 = 15. for n>6 calls will be more.

so, ans is 5

for n=5 stack will not overflow, n>5 stack will overflow.

Comments

when a call returns the activation record space is retrieved.

Answer 3

Number of activation records in the stack = 64/4 = 16

For every function call we maintain 1 stack entry but,

       Number of activation records needed in the recursive stack

                 = height of the tree + 1 (since height is starting from 0)

                 = number of levels in the tree

So maximum value of n for which number of levels in the tree <= 16 is 16 since

if n = k, number of levels in the recursion tree = k