尾遞歸vs原始遞歸

Question

我正在研究haskell遞歸。當我閱讀關於遞歸主題時，談論這兩種不同類型的遞歸。我很理解尾遞歸是如何工作的，以及它要完成的步驟。我不明白如何在後臺完成原始遞歸。任何人都可以在這裏幫助解釋更多關於原始和給出一些例子？ 例如：總和[1,2,3,4]的尾遞歸

sum:: [Int] -> Int 
sum [] = 0 
sum (x:xs) = x+ (sum xs) 

過程：

= 1 + sum[2,3,4] 
    = 1 + (2 + sum [3,4]) 
    = 1 + (2 + (3 + sum[4])) 
    = 1 + (2 + (3 (4 + sum[]))) 
    = 1 + (2 + (3 + (4 + 0))) 
    = 10 

如何原始遞歸的作品？

Answer 1

直覺上，當我們有遞歸函數時，我們有尾遞歸，當執行遞歸調用時，該調用的結果是函數的結果。從某種意義上說，在遞歸調用「沒有更多事情要做」之後。

-- tail recursion 
f1 n = if ... then ... else f1 (n - 1) 
-- not tail recursion 
f2 n = if ... then ... else 5 * f2 (n - 1) 

原始遞歸是另一個野獸。當每次遞歸調用都使用一個參數，它是原始參數的「直接子項」時，我們有原始遞歸。

-- primitive recursion (& non-tail recursion) 
f1 (x:xs) = g x (f1 xs) -- xs is asubterm of x:xs 

-- a tree type 
data T = K Int T T 
-- primitive recursion (& non-tail recursion) 
f2 (K n l r) = h n (f2 l) (f2 r)     -- l, r are subterms 
-- non-primitive recursion (& tail recursion) 
f3 (K n l (K m rl rr)) = f3 (K m (K n rl l) rl)  -- not a subterm