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()?

Let $T(n)$ denote the total number of invocations of the function get() when get(n) is executed.

From the function definition:

• For $n < 1$ ($n \le 0$), the function immediately returns after 1 invocation:

  $$T(n) = 1 \quad \text{for } n \le 0$$

• For $n \ge 1$, the function executes 1 call itself and invokes get(n-1) and get(n-3):

  $$T(n) = 1 + T(n-1) + T(n-3)$$

Now, we compute $T(n)$ bottom-up for $n = 0, 1, 2, 3, 4, 5, 6$:

• $T(\le 0) = 1 \implies T(0) = 1, T(-1) = 1, T(-2) = 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$

Thus, get() is invoked 25 times, which corresponds to option (B).