尾递归与原始递归
尾递归与原始递归
提问于 2015-12-15 03:51:30
我在研究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原始递归是如何工作的？
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-12-15 08:51:35
直观地说，当我们有一个递归函数时，我们有尾递归，这样，当执行递归调用时，调用的结果就是函数的结果。从某种意义上说，在递归调用“没有什么可做的”之后。
-- 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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34280832
复制相关文章
相似问题
腾讯云开发者
