尾遞歸與迭代算法

我找不到文章描述爲什麼尾遞歸函數應該優於迭代算法。尾遞歸與迭代算法

我不問爲什麼尾遞歸比簡單遞歸更好，我認爲這是無處不在的解釋。

那麼，爲什麼

sum(n) = { 
    def sumImpl(n, acc) = if(n <= 0) acc else sumImpl(n - 1 , n + accumulator) 
    sumImpl(n, 0) 
}

最好

sum = 0; 
while(n--) sum += n

來源

2012-10-15 raisercostin

你確定代碼是正確的？對我來說，看起來'sum（n）'總是會返回0. – phant0m

你是對的。我更新到良好的版本：D – raisercostin

遞歸使得程序更具可讀性，但它給表現不佳。迭代過程具有良好的性能，但不具有可讀性，可能需要局部變量來存儲中間值（可變性）。使用尾遞歸你將得到兩全其美的好處，並且不需要「總和」變量（不變性）。這在計算大數和或階乘時非常有用，因爲您只需將結果轉發給下一個遞歸函數調用就不會遇到stackoverflow異常。

在並行環境中，不變性非常重要。嘗試編輯您的代碼並將非常大的數字傳遞給該函數以查看差異。

延伸閱讀here

來源

2012-10-16 02:45:07 sgud

在前面的情況下，功能aproach不是更具可讀性。我仍然應該選擇那個版本？ – raisercostin

你的例子很簡單。在這種情況下，迭代是明顯的選擇。要看到迭代，遞歸，尾遞歸調用之間的差異，請嘗試這一個。 http://ideone.com/i0md7 – sgud

所以你是說尾部遞歸可以比迭代更有效率（斐波那契的6倍多）？斐波那契 - 位置：10000時間：137275432 ns 斐波納契塔 - 位置：10000時間：20357861 ns 我會檢查自己：D。謝謝 – raisercostin

尾遞歸與迭代算法

回答

相關問題