Question

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

Note: Ignore syntax errors (if any) in the function.

Hint:

Track the recursion by the value of length modulo 3: a "+1" is only added when length is 1 mod 3, and after that step the remainder can only cycle between 0 and 2, so it can never hit 1 again.

Answer 1

Correct Answer: 1

Step 1: Try a few small lengths by hand and watch the pattern.
Let $L=end+1-start$ be the length of the range on each call. Take a starting point where $start=0$ so we can just vary $end$.
$L=0$ or negative: returns $0$ straight away (base case).
$L=1$ (so $end=0$): $1 \bmod 3=1$, so this call returns $1+func(0,-1)$. The inner call has $end=-1$, which is negative, so it returns $0$. Total: $1$.
$L=2$ (so $end=1$): $2\bmod 3=2$, so this call returns $func(2,1)$, whose length is $0$, so it returns $0$. Total: $0$.
$L=3$ (so $end=2$): $3\bmod 3=0$, so this call returns $func(1,2)$, a new call with length $2$, which from above returns $0$. Total: $0$.
$L=4$ (so $end=3$): $4\bmod 3=1$, returns $1+func(0,2)$. The inner call has length $3$, which from above returns $0$. Total: $1$.

Step 2: Spot the rule from these trials.
Only lengths with remainder $1$ mod $3$ ever produce a nonzero result, and even then the answer is always exactly $1$, never more, because every call that follows a "+1" step lands on a length with remainder $0$ mod $3$, and lengths with remainder $0$ or $2$ never trigger another "+1" (they only feed into each other, as seen in the $L=2$ and $L=3$ trials above, both of which returned $0$).

Step 3: Confirm no larger value is possible.
Since remainder $1$ can only appear once before permanently switching into the $0/2$ cycle that adds nothing further, the running total can never exceed $1$, for any choice of start and end.

Step 4: State the maximum.
The largest value this function can ever return is
\[ \boxed{1} \]