1
我正在研究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