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

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

第一个递归从其末尾 (n) 开始对值 [0..n] 求和，如下所示:

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

使用这种方法，程序首先必须枚举所有数字，生成完整序列，然后才能真正执行加法。

这需要 O(n) 内存和 O(n) 时间。

在第二次递归中，我们像之前那样从 0 计数到 n，但现在我们边走边对数字求和，就像在

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

在数到 3 之前，我们可以对 1+2 求和。之后，我们可以只保留前面的和 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 这样的惰性语言中并不总是一个好主意，但如果传递的数据很简单，例如像数字而不是列表，尾递归通常是有益的。)