sml - 为什么一个折叠尾递归而另一个不是？

Question

fun fold1 f acc lst =
    case lst of
         [] => acc
       | hd::tl => fold1 f (f (acc,hd)) tl

fun fold2 f acc lst =
    case lst of
         [] => acc
       | hd::tl => f (fold2 f acc tl, hd)

为什么第一个是尾递归而另一个不是？

我认为它们都是尾递归的。

标签： smltail-recursionsmlnj

Answer 1

第一个是尾递归的，因为递归调用 (to fold1) 出现在函数体的末尾（它形成了“尾”）：

fold1 f (f (acc,hd)) tl

首先调用f (acc,hd)，然后将结果（连同fand tl）传递给fold1. 这是函数做的最后一件事；递归fold1调用的结果被传递给我们的调用者。

---

第二个不是尾递归的，因为递归调用 (to foldl2) 不是函数做的最后一件事：

f (fold2 f acc tl, hd)

首先调用fold2 f acc tl，然后从结果中创建一个元组hd，然后将该元组传递给f.

递归调用之后会发生两件事fold2：元组构造 ( (..., hd)) 和另一个函数调用 ( f ...)。特别是，调用的结果fold2不会直接传递给我们的调用者。这就是为什么这段代码不是尾递归的。