Dynamic programming

Question

Consider the following recursive function which is used by dynamic programming:

T(n)= 0 ;if n<1

       = 1;if n=1

      =T(n-1)+T(n-2)+1 ;if n>1      

Assume for every function call  T(i) it checks the table first, if its value is already computed it retrieves the value from table. Otherwise it calls a recursive function call to compute its return value. Whenever a function computes for first time its return value is stored in the table to avoid the redundant function calls. If system allocated 48 bytes for stack allocation, then the maximum value of ‘n’ so that overflow cannot occur ________. (Assume system allocate 4 byte to each stack entry which is sufficient for storing required data.)

Comments

N=13??

i followed tree method. But not sure about pushing T(0) and T(1) into stack.

---

@ashwin

stack allocation is 48 bytes. What does it mean?

You can use up to 48 bytes only. If it is true then 13*4 = 52 bytes.
How can it possible?

---

I am getting 13 without considering the main function and 12 with considering it.

---

max value will be, $n=12$ for no overflow.

@Ashwin, draw for n=4, you will see that maximum levels in recursion tree are 4(which shows that at any time atmost 4 entries will be present on recursion stack).

and also both f(1) and f(0) are pushed on stack for the first time, because without pushing their activation record on stack you can't evaluate them

---

Nitish Sir ..do we take main() into consideration for such cases?

---

i think it is asking the stack memory for functions excluding main()

---

Sir then following the tree method T(1) will be pushed onto the stack before T(0) right?
And there is no call to another function from T(1), T(1) after returning value pops out from stack and T(0) gets placed on the same stack space..so basically T(1) and T(0) are accommodated in the same area.
So shouldn't it be 13 then? Because 1 stack area for T(1) and T(0) and rest 11 stack area for different T(n). So 2+11 =13.

Edit :- Understood.. I was taking no. Of n values stack can take.. i.e. from n to 0 which is n+1.

---

@ joshi_nitish i tried on a stack ith n=5 ...T(0) will also enter the stack .. so i think maximum n should be 11.

---

with n=5,

maximum functions call that can be on stack at any time is 5, viz f(5)->f(4)->f(3)->f(2)->f(1)

f(0) will not increase stack level form 5 to 6 because f(0) will be pushed only after removal of f(1)

---

thanks for the correction ..yes it's 12.

---

@joshi_nitish

Consider this line --> Whenever a function computes for first time its return value is stored in the table to avoid the redundant function calls.

So when we are calculating T(12) it must also be pushed into the stack, but in the stack there we have already T(0) to T(11), so how can we further push T(12)?