为什么基于参数的定义比递归更高效？

Question

我有一个递归函数sumdown :: Int - > Int，它返回 所有自然数从它的参数的总和降到零，例如， sumdown 3应该返回和3 + 2 + 1 + 0 = 6

sumdown :: Int -> Int 
sumdown 0 = 0 
sumdown x = x + sumdown(x-1) 

我也有这个定义，我不完全了解，可能有人请评价这对我，告诉我为什么它比可能更有效上面的定义？

sumdown n = sumd n 0 
sumd 0 a = a 
sumd n a = sumd (n-1) (n+a) 

谢谢。

Answer 1

第一递归总和值[0..n]从其端部（n）开始，这样的：

1+(2+(3+(... + ((n-1) + n)) ...))) 

通过这种方法，程序首先必须枚举所有的号码，产生全序列，只有经过这些添加可以实际执行。

这需要O（n）内存和O（n）时间。

在第二递归，我们指望从0到n，因为我们没有较早，但现在我们在

(((1+2)+3)+4)+ ... 

总结数字，因为我们去，就像我们可以总结1+2我们数到3之前。之后，我们只能保留前面的金额1+2的结果，并从内存中丢弃号码1和2。因此，在整个过程中，我们只保留记忆1）迄今为止所达到的数字总和的结果，以及2）序列中的下一个数字。因此，我们现在只需要O（1）个存储器和O（n）时间。

注意：由于Haskell是惰性的，只有在每次递归时实际强制部分和才能使用上述参数。编译器优化器可以静静地添加这个强制，但是明确地说明它是个好主意，例如，在

sumdown n = sumd n 0 
sumd 0 !a = a 
sumd n !a = sumd (n-1) (n+a) 
-- here I am using the BangPatterns extension, 
-- otherwise, seq can be used instead 

第二次递归通常被称为“累加器式”，这是“尾递归”的一个特例。

（注2：尾递归并不总是在一个慵懒的语言象Haskell是个好主意，但如果各地传递的数据是简单的，如相同的数字，而不是像列表，尾递归通常是有益的。）

Answer 2

第二个函数是尾递归的，如果你遵循缩减步骤，它更好地执行的原因是清晰可见的。 （虽然由于哈斯克尔懒惰的性质，以下不是纯粹正确的，但它给的递归函数如何尾部可以更有效率的想法。）

sumdown 3 
// 3 + sumdown 2 
// 3 + (2 + sumdown 1) 
// 3 + (2 + (1 + sumdown 0) 
// 3 + (2 + (1 + 0)) 
// 3 + (2 + 1) 
// 3 + 3 
// 6 


sumdown 3 0 
// sumdown 2 3 
// sumdown 1 5 
// sumdown 0 6 
// 6 

此外，在大多数语言中，尾递归码被优化以重用相同的堆栈（因为它是递归函数的最后一个操作）。