###### Sliding-Window-Protocol

September 9, 2024###### Error-Control-Methods

September 10, 2024# GATE 1991

Question 10 |

Consider the following recursive definition of fib:

fib (n) : = if n = 0 then 1 else if n = 1 than 1 else fib (n – 1) + fib (n – 2)

The number of times fib is called (including the first call) for an evaluation of fib (7) is ___________

41 |

Question 10 Explanation:

The recurrence relation for the no. of calls is

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

Correct Answer: A

Question 10 Explanation:

The recurrence relation for the no. of calls is

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

Subscribe

Login

0 Comments