在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中調用遞歸函數

回答

相關問題