Short-circuited operators and tail recursion

Question

Say I have a simple function:

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 understandable 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 no zero difference between them; if bools contains only TRUE or FALSE (reasonably defined), they do the same.

My question is: if the 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 "& &" are short circuits? Obviously, if the operator were used without a short circuit, this would not be tail recursion, because both expressions would be evaluated before the operator is applied, but I am curious about the case with a short circuit.

(Before I get a stream of comments telling me that C compilers usually don’t optimize tail recursive calls: consider this as a general question about optimizing tail recursive calls with short circuit operators, regardless of language. 'I’m happy to rewrite this in Scheme, Haskell, OCaml, F #, Python, or what the hell else if you don't understand C.)

Answer 1

Your question is really "how smart is the compiler?" but you do not indicate which compiler you are using.

Given a hypothetical reasonable compiler that converts the source code to an intermediate stream graph before optimization, both pieces of code you wrote can be represented in the same way (the && operator, convenient for input, is not almost as trivially compiled as the operator and, so I won’t be surprised if it will be expanded in one phase on a hypothetical compiler). Based on this assumption, it is reasonable to say that the answer to your question is yes.

However, if you really rely on this, you should simply test it with any compiler that you use.