尾递归与原始递归

Question

我正在研究有关haskell的递归.当我读到关于这两种不同类型的递归的递归主题.我理解尾递归是如何工作的以及它要做的步骤.我不明白如何在后台完成原始递归.这里的任何人都可以帮助解释有关原始的更多信息吗？例如:尾递归

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

和[1,2,3,4]的过程:

  = 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