c++ - 在 std::function 中调用递归函数

Question

我刚刚使用 C++11/14 std::thread 对象编写了一个线程池，并使用了工作队列中的任务。在 lambda 表达式中调用递归函数时，我遇到了一些奇怪的行为。如果您以递归方式(使用 clang 3.5 和 gcc 4.9)实现 fac()，则以下代码会崩溃:

#include <functional>
#include <vector>

std::size_t fac(std::size_t x) {
    // This will crash (segfault).
    // if (x == 1) return 1;
    // else return fac(x-1)*x;

    // This, however, works fine.
    auto res = 1;
    for (auto i = 2; i < x; ++i) {
        res *= x;
    }

    return res;
}

int main() {
    std::vector<std::function<void()> > functions;

    for (auto i = 0; i < 10; ++i) {
        functions.emplace_back([i]() {  fac(i); });
    }

    for (auto& fn : functions) {
        fn();
    }

    return 0;
}

但是，它确实可以与上面的迭代版本一起正常工作。我错过了什么？

Answer 1

for (auto i = 0; i < 10; ++i) {
    functions.emplace_back([i]() {  fac(i); });

第一次 通过该循环时，i 将被设置为零，因此您正在执行:

fac(0);

使用递归定义这样做:

if (x == 1) return 1;
else return fac(x-1)*x;

表示 else block 将执行，因此 x 将环绕到任何最大 size_t 值(因为它是无符号的) .

然后它将从那里向下运行到 1，每次消耗一个堆栈帧。 至少，这将消耗 65,000 个左右的堆栈帧(基于标准中 size_t 的最小允许值)，但可能更多，很多 更多。

这就是导致您崩溃的原因。修复相对简单。由于 0! 被定义为 1，您只需将语句更改为:

if (x <= 1)
    return 1;
return fac (x-1) * x;

---

但您应该记住，递归函数最适合解决方案空间快速减少的情况，一个典型的例子是二分查找，每次递归时解决方案空间都会减半.

不会快速减少解决方案空间的函数通常容易出现堆栈溢出问题(除非优化器可以优化递归)。如果你传入足够大的数字，你可能仍然会遇到问题，这与将两个无符号数字加在一起并没有什么不同(尽管我实际上在很多个月前看到它作为递归示例提出):

def addu (unsigned a, b):
    if b == 0:
        return a
    return addu (a + 1, b - 1)

因此，在您的情况下，我会坚持使用迭代解决方案，尽管它没有错误:

auto res = 1;
for (auto i = 2; i <= x; ++i)   // include the limit with <=.
    res *= i;                   // multiply by i, not x.