Short-circuited operators and tail recursion

Question

Let's say I have a simple function like this:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    return *bools && all_true(bools+1, len-1);
}

This function can be rewritten in a more obviously tail-recursive style as follows:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    if (!*bools) return FALSE;
    return all_true(bools+1, len-1);
}

Logically, there is zero difference between the two; assuming bools contains only TRUE or FALSE (sensibly defined), they do exactly the same thing.

My question is: if a compiler is smart enough to optimize the second as a tail-recursive call, is it reasonable to expect it to optimize the first in the same way, given that "&&" short-circuits? Obviously, if a non-short-circuiting operator were used, this would not be tail-recursive because both expressions would be evaluated before the operator is even applied, but I'm curious about the short-circuited case.

(Before I get a flood of comments telling me that C compilers don't usually optimize tail-recursive calls: consider this to be a general question about optimizing tail-recursive calls with short-circuit operators, independent of language. I'll be happy to rewrite this in Scheme, Haskell, OCaml, F#, Python, or what the heck ever else for you if you don't understand C.)

Lakendra

gcc does optimise recursive calls. – Staffard

Answer 1

Your question is really "how smart is the compiler?" but you don't state which compiler you are using.

Given a hypothetical reasonable compiler which converts source code to an intermediary flow graph before optimizations, both fragments of code that you have written could be represented in the same way (the && operator, while convenient to type, is not nearly as trivially compiled as the & operator; so I wouldn't be surprised if it gets expanded out in one phase on a hypothetical compiler). On that assumption, it is reasonable to assert that the answer to your question is "yes".

However, if you're actually going to rely on this, you should just test it with whatever compiler you happen to be using.

Marianelamariani