What is printed by this C code: int c = 0; int fib(int n) { c++; return n < 2 ? n : fib(n – 1) + fib(n – 2); } int r = fib(5); printf(“%d %d”, r, c);?
Correct answer A. 5 15
Explanation
fib(5) is 5. The number of calls C(n) satisfies C(n) = 1 + C(n - 1) + C(n - 2) with C(0) = C(1) = 1, giving C(2) = 3, C(3) = 5, C(4) = 9 and C(5) = 15. Storing fib(5) in r first avoids depending on the unspecified order of evaluation of printf arguments. This exponential growth is why naive recursive Fibonacci is slow.
Answer checked How we write and check questions
Discussion