2014-12-08 12 views
1

我剛剛使用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()下面的代碼崩潰。我錯過了什麼?

+6

,而您的最終狀態是'X == 1'是不是因爲你從0開始? – Jamboree 2014-12-08 01:33:22

+0

重申你的最後一句話,如果「正常工作」的意思是「不會崩潰」,那麼你是正確的。如果它的意思是「給出正確的答案」,請參閱我的答案,爲什麼你可能想重新考慮這個陳述:-) – paxdiablo 2014-12-08 02:29:10

回答

4
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. 
3

這兩個定義對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)。

+0

[爲什麼打個招呼。停留片刻。永遠留下!](https://www.youtube.com/watch?v=i1_fDwX1VVY) – Yakk 2014-12-10 15:11:05

+0

@Yakk:到底是什麼!? – 2014-12-10 15:17:59

+0

@LightnessRacesinOrbit只是描述了將2^64-1再次遞減到1所花費的時間。以每秒80億次的速度遞減,大約68年:該程序可能會首先耗盡堆棧空間。 – Yakk 2014-12-10 15:23:10

1

遞歸版本不照顧的情況下對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; 
}