爲什麼基於參數的定義比遞歸更高效？

Question

我有一個遞歸函數sumdown :: Int - > Int，它返回 所有自然數從它的參數的總和降到零，例如， sumdown 3應該返回和3 + 2 + 1 + 0 = 6

sumdown :: Int -> Int 
sumdown 0 = 0 
sumdown x = x + sumdown(x-1) 

我也有這個定義，我不完全瞭解，可能有人請評價這對我，告訴我爲什麼它比可能更有效上面的定義？

sumdown n = sumd n 0 
sumd 0 a = a 
sumd n a = sumd (n-1) (n+a) 

謝謝。

Answer 1

第一遞歸總和值[0..n]從其端部（n）開始，這樣的：

1+(2+(3+(... + ((n-1) + n)) ...))) 

通過這種方法，程序首先必須枚舉所有的號碼，產生全序列，只有經過這些添加可以實際執行。

這需要O（n）內存和O（n）時間。

在第二遞歸，我們指望從0到n，因爲我們沒有較早，但現在我們在

(((1+2)+3)+4)+ ... 

總結數字，因爲我們去，就像我們可以總結1+2我們數到3之前。之後，我們只能保留前面的金額1+2的結果，並從內存中丟棄號碼1和2。因此，在整個過程中，我們只保留記憶1）迄今爲止所達到的數字總和的結果，以及2）序列中的下一個數字。因此，我們現在只需要O（1）個存儲器和O（n）時間。

注意：由於Haskell是惰性的，只有在每次遞歸時實際強制部分和才能使用上述參數。編譯器優化器可以靜靜地添加這個強制，但是明確地說明它是個好主意，例如，在

sumdown n = sumd n 0 
sumd 0 !a = a 
sumd n !a = sumd (n-1) (n+a) 
-- here I am using the BangPatterns extension, 
-- otherwise, seq can be used instead 

第二次遞歸通常被稱爲「累加器式」，這是「尾遞歸」的一個特例。

（注2：尾遞歸併不總是在一個慵懶的語言象Haskell是個好主意，但如果各地傳遞的數據是簡單的，如相同的數字，而不是像列表，尾遞歸通常是有益的。）

Answer 2

第二個函數是尾遞歸的，如果你遵循縮減步驟，它更好地執行的原因是清晰可見的。 （雖然由於哈斯克爾懶惰的性質，以下不是純粹正確的，但它給的遞歸函數如何尾部可以更有效率的想法。）

sumdown 3 
// 3 + sumdown 2 
// 3 + (2 + sumdown 1) 
// 3 + (2 + (1 + sumdown 0) 
// 3 + (2 + (1 + 0)) 
// 3 + (2 + 1) 
// 3 + 3 
// 6 


sumdown 3 0 
// sumdown 2 3 
// sumdown 1 5 
// sumdown 0 6 
// 6 

此外，在大多數語言中，尾遞歸碼被優化以重用相同的堆棧（因爲它是遞歸函數的最後一個操作）。