短路运算符和尾递归 [英] Short-circuited operators and tail recursion

问题描述

假设我有一个简单的函数，如下所示：

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);
}

逻辑上，两者之间的差为零；假设布尔值仅包含 TRUE 或 FALSE （合理定义） ，它们的作用完全相同。

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.

（在我收到大量评论告诉我C编译器通常不优化尾递归调用之前：认为这是有关优化tail的一般问题短路运算符的递归调用，与语言无关。我很乐意用Scheme，Haskell，OCaml，F＃，Python或如果您不懂C的语言重写它。）

(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.)

推荐答案

您的问题实际上是编译器有多聪明？

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.

这篇关于短路运算符和尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！