Test by Bikram | Mock GATE | Test 1 | Question: 11

Question

Consider following recursive functions:

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

The above function is run on a computer with a stack of $x$ bytes. Assume that only return address & parameter are passed on the stack and an integer value & return value take $2$ $bytes$ each. If we can execute this function for maximum value $n = 10$ without overflowing the stack. Then the size of the stack is ______ $Bytes$.

Comments

@ nice question

---

Gate similar question

https://gateoverflow.in/2517/gate1994_21

Answer 1

" All computer really needs to remember for each active function call is values of arguments & local variables and the location of the next statement to be executed when control goes back" .

read this  slide number 3 and 4 -->http://www-inst.eecs.berkeley.edu/~cs164/fa12/ta-materials/recursionOnStack.ppt  .

Here we have n = 10, running successfully, meaning function calls from $n = 1,2,\dots ,10$ can be live at a time on stack (maximum recursion depth and not total no. of recursive calls). So, this should mean a minimum stack space of $10 \times 4 = 40$ bytes.

Comments

My question is :

for,

fib(0) = 1 function call,

fib(1) = 1 function calls,

fib(2) = 2 function calls,

fib(3) = 4 function calls,

fib(4) = 8 function calls,

fib(5) = 16 function calls,

--------------------------------

fib(10) = 512 function calls,

are made , so can't we consider it as 512*(2+2)=2048 Bytes in total for the stack?

---

u can better understand this by recursion tree, the calls on same level in tree, will be on same stack height..

 

so its the height of the tree that matters, not the calls

---

Nice question Sir!

---

@bikram Sir why didnt u include f(0) ??

function calls are from 0 to 10. and return values from 1 to 10 so it must be 11(2) + 10(2) = 42 bytes.

Answer 2

Answer should be 36 Bytes, because f(1) and f(0) won't be pushed on stack,
when the function call is f(2), and f(2) calls f(1) then F(2) will be pushed to stack but why should we push f(1) when there is no call after f(1).
@Bikram @Arjun please clear the doubt

Comments

sir plz provide the complete soltution that would be more helpful

---

@priyanka gautam-piya 

please do the calculation with the help of below gate question , i have no time now :( 

similar  Gate question

https://gateoverflow.in/2517/gate1994_21

---

@Bikram fib(1) needs to be there in the stack as functions after it will be using it so why fib(0) is left out?? Since it will be used in the computation of fib(2).