Question

Considering the following function, if you perform a breadth first scan of its recursion tree for call f(5), what would be
the maximum size of the queue, at any given time?
int f (int n) {
return (n < 3) ? n-1 f(n-1) + f(n-2);
}​

Answer 1

Answer:

Considering the following function, if you perform a breadth first scan of its recursion tree for call f(5), what would be

the maximum size of the queue, at any given time?

int f (int n) {

return (n < 3) ? n-1 f(n-1) + f(n-2);

}

Explanation:

mark as brainliest

Answer 2

Answer:

Method:

Ans is $n=5 .$

size of activation record $=2+2=4$ bytes

size of stack = 64 bytes

so,$\frac{64}{4}=16$ activation records we can push.

no of activation records $=$ no of recursive calls

and no of recursive calls for Nth Fibonacci num is $=2 * f i b(n+1)-1$

here it should be less than $16$ , if we take $n=5$ then no of rec calls are $2 * f i b(6)-1=15$. for $n > 6$calls will be more.

so, ans is 5

for $n=5$ stack will not overflow, $n > 5$stack will overflow.

Method 2:

Size of an activation $=2+2=4$ record bytes.

So, no. of possible activation records which can be live at a time $=64 / 4=16 .$

So, we can have 16 function calls live at a time (recursion depth $=16$ ), meaning the maximum value for $n$ without stack overflow is 16 (calls from $1-16$ ). For $n=17$, stack will overflow.

This is different from the total no. of recursive calls which will be as follows: