GATE CS 2026 Set 2 Q.61: Functions, Recursion, Scope and Storage Classes

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.

Your answer

Official answer and solution

Official answer: 1
From: Official GATE 2026 answer key

Solution

Track how length = end + 1 - start changes modulo 3 in each recursive branch.

Let $L = \text{length} = \text{end} + 1 - \text{start}$ . Whenever $L < 1$ or $\text{start} < 0$ or $\text{end} < 0$ , func returns $0$ . For $L \ge 1$ :

If $L \equiv 2 \pmod 3$ : the else branch calls func(start + 2, end), which reduces $L$ by $2$ without adding to the return value, giving $L' = L - 2 \equiv 0 \pmod 3$ .
If $L \equiv 0 \pmod 3$ : the first branch calls func(start + 1, end), which reduces $L$ by $1$ without adding to the return value, giving $L' = L - 1 \equiv 2 \pmod 3$ .
Thus any call starting with $L \equiv 0$ or $L \equiv 2 \pmod 3$ alternates between $0 \pmod 3$ and $2 \pmod 3$ (decreasing $L$ by $1$ , then $2$ , then $1$ , ...) until $L \le 0$ , returning $0$ !
If $L \equiv 1 \pmod 3$ : the else if branch returns 1 + func(start, end - 1), which adds $1$ and reduces $L$ by $1$ to $L' = L - 1 \equiv 0 \pmod 3$ . By the case above, the recursive call with $L' \equiv 0 \pmod 3$ always returns $0$ !

Therefore, func returns at most $1 + 0 = 1$ for any inputs.

Final answer

Common trap

Assuming the length % 3 == 1 branch can be visited multiple times when in fact it transitions immediately to length % 3 == 0, which then cycles between $0$ and $2 \pmod 3$ .

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

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 61 of 65
Section: Computer Science and Information Technology

Report an error in this question

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

Question

Solution

Source