尾递归vs原始递归

问题描述：

我正在研究haskell递归。当我阅读关于递归主题时，谈论这两种不同类型的递归。我很理解尾递归是如何工作的，以及它要完成的步骤。我不明白如何在后台完成原始递归。任何人都可以在这里帮助解释更多关于原始和给出一些例子？例如：总和[1,2,3,4]的尾递归尾递归vs原始递归

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

如何原始递归的作品？

它们不是不同的类型，尾递归函数是所有递归函数的一个子集。它们可以通过编译器转换为循环，因此不会消耗堆栈。 – fjarri

@fjarri因为懒惰而没有那么清晰。 – Cactus

'sum'不是尾递归的;那将是'sum = go 0 where go acc [] = acc;去acc（x：xs）= go（x + acc）xs' – Cactus

答

直觉上，当我们有递归函数时，我们有尾递归，当执行递归调用时，该调用的结果是函数的结果。从某种意义上说，在递归调用“没有更多事情要做”之后。

-- 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

尾递归vs原始递归

相关推荐