尾递归与 List.fold_left
Tail recursion vs List.fold_left
我无法理解尾递归和 List.fold_left 之间的区别？
有什么区别？什么时候应该使用尾递归以及什么时候 List.fold_left?
List.fold_left 是迭代序列的函数概括。它是一个函数，它接受一个列表，一些初始值，并将此函数按顺序应用于列表的每个元素。这是函数式编程中众所周知的 higher order 函数。而且它通常用于循环和迭代而不是直接使用递归。
尾递归是尾调用的一种特殊情况，当对函数本身进行调用时。基本上，调用是尾部，如果它是函数中的最后一个表达式。这样在调用之后就不需要执行任何更多的评估。尾调用在 OCaml 中进行了优化，迭代过于简单，即它们不像普通调用那样消耗堆栈。
List.fold_left是使用递归实现的，标准实现中所有的递归调用都在尾位置。还有一个 List.fold_right 有时会以非尾部递归方式实现。
如果你的问题是"what can I do using tail recursion that I can't using fold_left and vice versa"，答案是：
任何可以使用 fold_left 实现的东西都可以使用尾递归实现，因为 fold_left 本身通常使用尾递归实现。下面的东西可以用尾递归实现，但不能fold_left:
- 任何迭代列表以外的东西（假设你迭代直到整数为 0）。
- 任何你迭代列表的地方，但一次不是一个元素。
- 任何你迭代列表的地方，但你可以在到达结尾之前停止。
我无法理解尾递归和 List.fold_left 之间的区别？
有什么区别？什么时候应该使用尾递归以及什么时候 List.fold_left?
List.fold_left 是迭代序列的函数概括。它是一个函数，它接受一个列表，一些初始值，并将此函数按顺序应用于列表的每个元素。这是函数式编程中众所周知的 higher order 函数。而且它通常用于循环和迭代而不是直接使用递归。
尾递归是尾调用的一种特殊情况，当对函数本身进行调用时。基本上，调用是尾部，如果它是函数中的最后一个表达式。这样在调用之后就不需要执行任何更多的评估。尾调用在 OCaml 中进行了优化，迭代过于简单，即它们不像普通调用那样消耗堆栈。
List.fold_left是使用递归实现的，标准实现中所有的递归调用都在尾位置。还有一个 List.fold_right 有时会以非尾部递归方式实现。
如果你的问题是"what can I do using tail recursion that I can't using fold_left and vice versa"，答案是：
任何可以使用 fold_left 实现的东西都可以使用尾递归实现，因为 fold_left 本身通常使用尾递归实现。下面的东西可以用尾递归实现，但不能fold_left:
- 任何迭代列表以外的东西（假设你迭代直到整数为 0）。
- 任何你迭代列表的地方，但一次不是一个元素。
- 任何你迭代列表的地方，但你可以在到达结尾之前停止。