What is the output printed by the following program? #include<stdio.h> int…
2005
What is the output printed by the following program?
#include<stdio.h>
int f(int n, int k)
{
if (n == 0)
return 0;
else if (n % 2)
return f(n/2, 2*k) + k;
else return f(n/2, 2*k) - k;
}
int main ()
{
printf("%d", f(20, 1));
return 0;
}
- A.
5
- B.
8
- C.
9
- D.
20
Attempted by 23 students.
Show answer & explanation
Correct answer: C
Solution:
Trace the recursive calls for f(20, 1):
f(20, 1): 20 is even, so f(20,1) = f(10,2) - 1.
f(10, 2): 10 is even, so f(10,2) = f(5,4) - 2.
f(5, 4): 5 is odd, so f(5,4) = f(2,8) + 4.
f(2, 8): 2 is even, so f(2,8) = f(1,16) - 8.
f(1, 16): 1 is odd, so f(1,16) = f(0,32) + 16.
f(0, 32): base case returns 0.
Compute values while unwinding:
f(1,16) = 0 + 16 = 16
f(2,8) = 16 - 8 = 8
f(5,4) = 8 + 4 = 12
f(10,2) = 12 - 2 = 10
f(20,1) = 10 - 1 = 9
Final answer printed by the program: 9