in Algorithms
197 views
1 vote
1 vote

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.

in Algorithms
197 views

1 Answer

1 vote
1 vote

$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

edited by

2 Comments

How do you know T(0) and T(1) will share same space?
0
0
$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.
0
0

Related questions