1.6k views

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 | 1.6k views

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
0
Wondering should not it be 17 instead of 16 ? I mean, we need to push stack return address & parameters on stack only when we are calling another function  ?  So here in case if Fib(2) is calling FIb(1), Fib(2) Return address & Parameters are stored onto stack & Fib(1) are not ! Can you provide reference ? I got the calculation for 16, but not sure when exactly we are pushing stuff on stack !
+12
I didn't get what exactly you are asking. When we call a function we create its activation record. When function returns activation record is deleted.

A calls B. Now we create activation record for B on stack. This is used for local variables of B and also to store the return address. parameters are currently passed by registers and only when needed stack is used- in which case it also becomes part of activation record.
0
Yes you are correct !
0

But fib(1) is not calling another function so it need not require return address,but it will have parameters , because fib(2) is calling fib(1) so 1 will be passed as a parameter to fib(1) activation record.Return address only require when we are calling another function in between our program,because it keeps track of after returning from another function call then from where to start our execution of original program but fib(1) is simply returning 1 it need not have return address information to keep track of from where to execute our program when we return back.

I mean when function is called,its activation record already contain return address field ,parameters field etc. whether it is required or not.In fib(1) case return address is not required so what will it contain?either 0  or any other default value.

+3
Return address is for "self". i.e., to return to whoever called me. So, it should be there for all functions in C.
+1

fib(7) fib(6) fib(5) fib(4) fib(3) fib(2) fib(1) - 7 activation record

fib(7) fib(6) fib(5) fib(4) fib(3) fib(2) fib(1) fib(0) - 8 activation record(8*(2B+2B) = 32B consumed)

With 64B, 64/4=16 activation record can be at a time on stack at max.

i.e.(n+1)=16 -> n=15

+1
@Arjun sir.why activation record is of 2+2=4 Bytes only?

We will store the following in stack:-

1. n

2.return address (where to return after function call over)

3.Where will be store fib(n-1)? After calculating fib(n-1) ,we will call fib(n-2),so result of fib(n-1) must be stored somewhere,so that it can be added later,but we have not reserved this space anywhere.Can you please help in clearing this doubt?
+1
Because each time we are doing 2 function call and initially fib(0) and fib(1) initially takes value 1
0

@srestha  ,i mean when a function is called,n will be pushed.Now suppose it call f(5) ,which is f(4)+f(3) .So after it call f(4) ,we need f(3) also,so we should store both n and result of f(4) in stack,which means two variables +1 return address =12 Bytes.Please check

we should store both n and fib in stack

0

to be more clear on this, is this will be the sequence of depth (stack space)
fib(17),fib(16),fib(15).......................fib(2),fib(1),         option A
or
fib(16),fib(15),fib(14).......................fib(2),fib(1),         option B

help me!

+5

The below recursion tree will help you to get an idea of how many levels will suffice Assuming fib(n) is denoted as F(n) in the diagram,

I have taken an example of F(4).

Now, you know function calling sequence in recursion is in preorder and evaluation order is postorder.

Each recursive call of F(i) takes 4 bytes of storage on the stack where 2 bytes are taken by parameter i  and 2 bytes for the return address.

Even for the initial call, return address would be saved for F(i).

So, as we see from recursion tree, longest chain of recursion will be depicted by longest chain or leg of recursion tree and the number of levels in the recursion tree will tell, how many recursive calls will be active at a time in the stack.

Also, note, at each level, all the number of function calls will take only one unit of stack,

because function evaluation order being postorder,

LEFT, RIGHT, ROOT, return

So, now we need to find how many levels can we have in total where each level takes 4 bytes and total we can allow for 64 bytes of storage.

64/4=16 levels of recursion can be accommodated all at a time in the stack.

0
@Ayush ,can you clear my doubt above? while going to right of the tree we need to save the reuslt from left subtree.Why that value is not considered as a part of activation record?
0
yeah let's say F(3) is evaluated for F(4) now we need to go to F(2),

So, F(3)'s computed result will be stored in the activation record of F(4)

Since there is nothing mentioned about what we have to do for intermediate results, we cannot take storage space to be accounted for them.
0
But they also dont say you need to store n.I think these both are mandatory to be stored.Return value and local variable.Both are part of activation record.If we come back from recursion,then we need the f(3)'s result as you mentioned.So where will we get this from?Activation record,right?We dont have keys for these questions.So not sure if i am thinking right.:).But if the same comes now in numerical question,i would have considered space for both
+1
@Rahul, Yes I agree with your point. But the question setter what I think wants to project the below points

(1)The depth of recursion is limited by stack space.

(2)Recursive programs are not efficient because they take so much of stack space

(3)Another approach(like dynamic programming) in which we save results like there are many redundant function calls, inFib(n) but with DP they would be avoided calling multiple times. Only one-time call and result would be saved.

(4)Finally, they want to know what is the maximum recursion depth, or value of n for which this Fib(n) would execute without any exception.
0
we will approach like preorder traversal ......
0

Here F(n) = F(n-1) + F(n-2)

During the execution ..either Left of + (i.e F(n-1)) evaluated first or may be Right first (i.e F(n-2)) ..it is dependent on compiler right ..

Just like a = f() + g()

But in any case MAX activation records live at a time are 16 for n = 16

Am I right ?

0
yes
0

@Ayush Upadhyaya 's approach is correct...

+1 vote
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
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.
+12
when a call returns the activation record space is retrieved.