recategorized by
25,353 views
37 votes
37 votes

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.

recategorized by

3 Answers

Best answer
62 votes
62 votes
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}$$
edited by
4 votes
4 votes
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.
3 votes
3 votes
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
Answer:

Related questions

22 votes
22 votes
2 answers
3
Kathleen asked Oct 4, 2014
3,757 views
An unrestricted use of the "$goto$" statement is harmful becauseit makes it more difficult to verify programsit increases the running time of the programsit increases the...
26 votes
26 votes
2 answers
4