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

Answer: B. 25 — 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. A.

    15

  2. B.

    25

  3. C.

    35

  4. D.

    45

Attempted by 70 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:

  1. T(0) = 1

  2. T(1) = 1 + T(0) + T(-2) = 1 + 1 + 1 = 3

  3. T(2) = 1 + T(1) + T(-1) = 1 + 3 + 1 = 5

  4. T(3) = 1 + T(2) + T(0) = 1 + 5 + 1 = 7

  5. T(4) = 1 + T(3) + T(1) = 1 + 7 + 3 = 11

  6. T(5) = 1 + T(4) + T(2) = 1 + 11 + 5 = 17

  7. 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…