Official PYQ · 2026Set 2 · Q51RecursionNAT2 marks

GATE CS 2026 Set 2 Q51 — Recursion

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.

View worked solution

Answer: 1:1

Let $L = \text{end} + 1 - \text{start}$ represent the length of the interval. We can analyze the behavior of the function based on $L \pmod 3$ :

Case 1: $L \equiv 0 \pmod 3$
The function returns func(start+1, end). The new length is $L - 1 \equiv 2 \pmod 3$ .
Case 2: $L \equiv 2 \pmod 3$
The function returns func(start+2, end). The new length is $L - 2 \equiv 0 \pmod 3$ .
Case 3: $L \equiv 1 \pmod 3$
The function returns $1 + \text{func}(\text{start}, \text{end}-1)$ . The new length is $L - 1 \equiv 0 \pmod 3$ .

Let $V(L)$ be the value returned by the function for length $L$ (assuming $\text{start}, \text{end} \ge 0$ ):

\begin{aligned} V(3k) &= V(3k-1) \\ V(3k-1) &= V(3k-3) \\ V(3k+1) &= 1 + V(3k) \end{aligned}

Using the base case $V(L) = 0$ for $L < 1$ :

$V(1) = 1 + V(0) = 1 + 0 = 1$
$V(2) = V(0) = 0$
$V(3) = V(2) = 0$
$V(4) = 1 + V(3) = 1 + 0 = 1$
$V(5) = V(3) = 0$

By induction, $V(L) = 1$ if $L \equiv 1 \pmod 3$ , and $V(L) = 0$ otherwise. Any boundary cases where start or end becomes negative will only trigger the base case earlier, returning $0$ .

Thus, the maximum possible value that can be returned is 1.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Recursion questions

GATE CS 2026 Set 2 Q51 — Recursion

Related questions