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

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]从end(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

第二个函数是尾递归,如果你遵循简化步骤,它的表现更好的原因是清晰可见的.(虽然由于Haskell的惰性,以下不完全正确,但它给出了尾递归函数如何更有效的概念.)

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

此外,在大多数语言中,尾递归代码被优化为重用相同的堆栈(因为它是递归函数的最后一个操作).