有人可以像我五岁一样解释 OCaml 尾递归吗？

Question

我无法将我的大脑围绕尾递归，特别是在 ocaml 中，也解释了为什么人们在最后调用“in”函数。PS我说的是最基本的尾递归函数。

Answer 1

函数通过三种方法之一进行通信。

每次调用函数时，都会创建一个堆栈帧，其中包含该函数完成其工作所需的数据。完成后，其返回值将在堆栈“向上”返回给其调用者。

sum考虑一个对列表求和的简单函数。

let rec sum lst =
  match lst with
  | [] -> 0
  | x::xs -> x + sum xs

很简单。空列表的总和当然是0。非空列表的总和是第一个元素加上列表其余元素的总和。

当我们递归调用时，sum xs该调用不知道x是什么。它无法执行该添加操作。它只能对剩余列表求和，然后将其发送回堆栈以进行添加。

如果我们用一个小列表来做到这一点，那么这并不是什么问题。堆栈是有限的，但还没有限制到足以引起关注的程度。

但是，如果我们尝试使用包含大量元素的列表，我们将耗尽堆栈空间并收到错误。

该sum函数的尾递归版本需要确保其最后一次调用可以提供完整的答案，而无需返回信息备份堆栈。这意味着当调用函数时，调用者需要通过其参数将任何所需的信息传递给被调用者。

为了实现这一点，我们使用累加器，通常称为acc。

let rec tail_sum acc lst =
  match lst with 
  | [] -> acc
  | x::xs -> tail_sum (acc + x) xs

当tail_sum迭代列表时，它会不断累积总和。当列表为空时，它返回该累加器。我们只需要始终tail_sum以的起始累加器进行调用0。

tail_sum 0 [1; 2; 3; 4; 5; 6]

这很丑陋，因此您通常会通过使用本地嵌套辅助函数来看到它被隐藏。

let tail_sum lst =
  let rec helper acc lst =
    match lst with 
    | [] -> acc
    | x::xs -> helper (acc + x) xs
  in
  helper 0 lst

想象一下我在办公室工作。我的老板让我知道他的午餐什么时候准备好。

场景 1：我让秘书告诉我午餐什么时候准备好。他要求咖啡馆经理告诉他午餐什么时候准备好。咖啡馆经理要求厨师告诉她午餐什么时候准备好。他们都互相汇报，最终向我汇报，我告诉老板午餐什么时候准备好。

场景2：我让我的秘书告诉老板午餐什么时候准备好。我的秘书告诉咖啡馆经理午餐准备好后告诉老板。咖啡馆经理告诉厨师午餐准备好后告诉老板。厨师直接联系老板并提供所需信息。

场景 2 中更直接的方法是可能的，因为有关最终接收者的信息在每个阶段都会传递。同样的目的也达到了，只不过这一次一旦离开了每个人的手中，他们就可以忘记它了。它们不再是实现目标所必需的。