Question 7
Back to Exercise
What is the output of the following C program?
#include <stdio.h>
static int calls = 0;
int fib(int n) {
calls++;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main(void) {
int r = fib(6);
printf("%d %d\n", r, calls);
return 0;
}- A 8 25 Correct
- B 8 6
- C 13 25
- D 8 15
Correct Answer: Option A
fib(6) = 8. The naive version recomputes the same values again and again: it makes 2 × fib(7) − 1 = 25 calls for n = 6, and the count grows exponentially. Memoization brings it down to n + 1 calls.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!