在std :: function中调用递归函数

我刚刚使用C++ 11/14 std :: thread对象编写了一个线程池，并使用worker队列中的任务。在lambda表达式中调用递归函数时遇到了一些奇怪的行为。在std :: function中调用递归函数

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

它，然而，做工精细与上面的迭代版本：如果你在一个递归的方式（包括铿锵3.5和gcc 4.9）实现fac()下面的代码崩溃。我错过了什么？

来源

2014-12-08 Rosario Raulin

，而您的最终状态是'X == 1'是不是因为你从0开始？ – Jamboree 2014-12-08 01:33:22

重申你的最后一句话，如果“正常工作”的意思是“不会崩溃”，那么你是正确的。如果它的意思是“给出正确的答案”，请参阅我的答案，为什么你可能想重新考虑这个陈述:-) – paxdiablo 2014-12-08 02:29:10

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

的第一一次通过这个循环，i将被设置为零，所以你执行：

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

：

fac(0);

与递归定义这样做

意味着else块将执行，因此x将环绕到最大值size_t值是（因为它是无符号的）。

然后它将从那里运行到1，每次消耗一个堆栈帧。在最低，这将消耗65000左右的堆栈帧（基于最小允许值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.

来源

2014-12-08 01:46:49 paxdiablo

这两个定义对x=0都有不同的行为。循环将被罚款，因为它使用了小于操作：

auto res = 1; 
for (auto i = 2; i < x; ++i) { 
    res *= x; 
}

然而，在准无限循环

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

结果x == 1是假的，x-1产生的std::size_t最大可能值（通常为2 -1）。

来源

2014-12-08 01:33:19 Columbo

[为什么打个招呼。停留片刻。永远留下！]（https://www.youtube.com/watch?v=i1_fDwX1VVY） – Yakk 2014-12-10 15:11:05

@Yakk：到底是什么！？ – 2014-12-10 15:17:59

@LightnessRacesinOrbit只是描述了将2^64-1再次递减到1所花费的时间。以每秒80亿次的速度递减，大约68年：该程序可能会首先耗尽堆栈空间。 – Yakk 2014-12-10 15:23:10

递归版本不照顾的情况下对x == 0。

您需要：

std::size_t fac(std::size_t x) { 
    if (x == 1 || x == 0) return 1; 
    return fac(x-1)*x; 
}

或

std::size_t fac(std::size_t x) { 
    if (x == 0) return 1; 
    return fac(x-1)*x; 
}

来源

2014-12-08 01:47:36

在std :: function中调用递归函数

回答

相关问题