Recursive function

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 it's 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 T(i) computed for first time its return value is stored in the table to avoid 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

is the answer 6?

---

No , it's 12 given

---

The stack can contain 48/4= 12 entries right now if we try to compute T(6) then the stack contain 11 entries and if we go for T(7) then the stack needs >12 entries which can create the overflow . So n=6 is the least which can be computed without overflow.

---

@Kabir5454 bro 6 can't be the answer I think 

see this

Answer 1

The function calling is done in preorder while return value in given in post order meaning whenever we call T(n) then T(n-1) we be called first and T(n-2) will only be called once T(n-1) has returned value.

So we begin with n=12 then n=11 is called but n=10 waits until n=11 returns value,

Similarly n=11 calls n=10 but n=9 waits till n =10 returns value.

This goes one till n=1 where we get 1 as return value, so from 12 to 1 we have 12 function calls whose entry will reside in stack at same time and 12x4 =48 will be entry size.

the key point to keep in mind is the order of function calls which is preorder.

Here’s a similar question : GATE CSE 1994 | Question: 21 - GATE Overflow for GATE CSE

 

 

Comments

Got it 👍 , thanks