尾递归与List.fold_left

Question

我不明白尾递归和List.fold_left之间的区别？

有什么区别？我应该在什么时候使用尾递归和List.fold_left？

Answer 1

List.fold_left是迭代序列的泛函。它是一个函数，它接受一个列表，一些初始值，并将这个函数按顺序应用到列表中的每个元素。这是函数式编程中众所周知的higher order函数。它通常用于循环和迭代，而不是直接使用递归。

当函数本身调用时，尾递归是尾调用的一种特殊情况。基本上，一个调用是尾部的，如果它是函数中的最后一个表达式。所以在通话之后，不需要再进行任何评估。尾调用在OCaml中进行了简化的迭代，即它们不像正常的调用那样消耗栈。

List.fold_left是使用递归实现的，并且标准实现中的所有递归调用都位于尾部位置。还有一些是List.fold_right，有些时候是以非递归方式实现的。

Answer 2

如果你的问题是“我能做什么用，我不能使用fold_left，反之亦然尾递归”，得到的回答是：

凡是可以使用fold_left实现可以使用尾递归的实现fold_left本身通常使用尾递归来实现。以下几点可以使用尾递归来实现，但不是fold_left：

• 任何事情如果你遍历比列表以外的东西（比如你正在迭代直到整数为0）。
• 任何你迭代一个列表而不是一次一个元素的地方。
• 任何你迭代列表的地方，但你可能会停止，直到结束。