GATE 2026 CS (CS2) – Question 61

Programming and Data Structures · Recursion · 2 marks · Numerical answer

Consider the following ANSI C function.

int func(int start, int end){
    int length = end + 1 - start;
    if ((length < 1) || (start < 0) || (end < 0)) { return 0; }
    if (length % 3 == 0){
        return func(start + 1, end);
    } else if (length % 3 == 1){
        return 1 + func(start, end - 1);
    } else {
        return func(start + 2, end);
    }
}

The maximum possible value that can be returned from this function is __________. (answer in integer)

Note: Ignore syntax errors, if any, in the function.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 1

Explanation

Let $f(L)$ denote the return value when the current segment length is $L=end+1-start$. If $L<1$, the function returns 0. For $L\equiv0\pmod3$, it reduces to $f(L-1)$. For $L\equiv1\pmod3$, it returns $1+f(L-1)$. For $L\equiv2\pmod3$, it reduces to $f(L-2)$. Evaluating small values gives $f(0)=0$, $f(1)=1$, $f(2)=0$, $f(3)=0$, $f(4)=1$, and the pattern repeats with period 3. Hence the maximum possible return value is 1.