GATE Overflow Test Series | Programming | Test 1 | Question: 18

Question

The number of times the "return" statement gets executed when the following function is called with an argument $5$ is ______

unsigned int fib(unsigned int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

Answer 1

Total number of times return statement get executed $=15.$

 

Comments

Used the same approach in solving this question, just wondering is there any formula based(quicker) approach?

---

.

Answer 2

Number of times return statement getting executed is same as the number of calls to fib.

• fib(5) = fib(4) + fib(3) + 1
• fib(4) = fib(3) + fib(2) + 1
• fib(3) = fib(2) + fib(1) + 1
• fib(2) = fib(1) + fib(0) + 1
• fib(1) = 1
• fib(0) = 1

Now, going up we get,

• fib(2) = 3
• fib(3) = 5
• fib(4) = 9
• fib(5) = 15