GATE CS 2015 Set 3 Q.49 (CS Q.39): Functions, Recursion, Scope and Storage Classes

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

Official answer and solution

Solution

Formulate the recurrence relation for the total number of function calls and solve bottom-up.

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

For any $n < 1$ , get(n) is called once, tests if (n < 1) return;, and immediately returns without making any recursive calls.
Hence, $T(n) = 1$ for all $n \le 0$ .

For $n \ge 1$ , get(n) executes 1 call itself, followed by recursive calls get(n - 1) and get(n - 3): $T(n) = 1 + T(n - 1) + T(n - 3)$

Compute bottom-up:

$T(0) = 1, \quad T(-1) = 1, \quad 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, the function get() is invoked 25 times (Option B).

Final answer

Common trap

Omitting the base case calls where n < 1, which are full function invocations that execute the function prologue and base condition.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.