made easy test series

Question

How is the max possible value of n is 12? We will have to store T(0) and T(1) in stack too, so we can call f(11) at max which will require T(10) and T(9) and then we will store f(11) in stack. But if we call f(12) we wont be able to store it as overflow will occur.

Answer 1

$T_{0}=0\ ,\ T_{1}=1\ given\ in\ question $

Let's there is 

$T{_{2}}=T{_{1}}+T {_{0}}$

$T{_{1}}\ will\ call\ first\ and\ return\ 1\ and\ make\ space\ for \ T{_{0}}$

$it\  means\ T{_{1}}\ and\ T{_{0}}\ will\ share\ same\ space$

$say\ n=4$

$T_{1}$

$T_{2}$

$T_{3}$

$T_{4}$

 

$T_{1}\ and\ T_{0}\ values\ are\ store\  in\ table\ so \ no\ need\ to\ evaluate\ them.$

$in\ this\ question\ maximum\ number\ of\ function\ call\ before\ stack\ overflow\ is\ $

$n*4=48$

n=12

Comments

How do you know T(0) and T(1) will share same space?

---

$T{_{0 }}\ and\ T{_{1}}\ values \ given \ in\ question$ those values have to retrieve from table.

 In stack $T{_{1}}$ will come before $T{_{0}}$

It will fetch value from table and will free up space that will be used by $T{_{0}}$

PS: make a stack and perform operations on it.

Answer 2

Let n = 4                   T(4)

                     T(3)               T(2)

               T(2)      T(1)     T(1)    T(0)

          T(1)    T(0)

So for n=4  4 levels of stack needed. now for 12 levels stack n=12