Consider the following recursive C function. void get(int n) { if (n<1)…
2015
Consider the following recursive C function.
void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); }
If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
- A.
15
- B.
25
- C.
35
- D.
45
Attempted by 58 students.
Show answer & explanation
Correct answer: B
Let T(n) be the number of times get is invoked for input n.
Base case: For n < 1 the function returns immediately, but the call itself is counted, so T(n) = 1.
Recursive case: For n ≥ 1 the function calls get(n-1) and get(n-3) and counts the current call, so
T(n) = 1 + T(n-1) + T(n-3)
Compute values step by step from the base:
T(0) = 1
T(1) = 1 + T(0) + T(-2) = 1 + 1 + 1 = 3
T(2) = 1 + T(1) + T(-1) = 1 + 3 + 1 = 5
T(3) = 1 + T(2) + T(0) = 1 + 5 + 1 = 7
T(4) = 1 + T(3) + T(1) = 1 + 7 + 3 = 11
T(5) = 1 + T(4) + T(2) = 1 + 11 + 5 = 17
T(6) = 1 + T(5) + T(3) = 1 + 17 + 7 = 25
Therefore, get(6) is invoked 25 times before returning to main.
A video solution is available for this question — log in and enroll to watch it.