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

Question

我无法全神贯注于尾递归，特别是在 ocaml 中也解释了为什么在最后调用“in”函数。 P.S。我说的是最基本的尾递归函数。

Answer 1

尾调用是函数中的最后一个表达式，它成为整个函数的结果，例如

let foo x = x + 1
let bar x = 
  let x = x + 1 in
  foo x (* here foo is in the tail position *)

当调用位于尾部位置时，可以非常便宜地进行调用，而无需在程序堆栈上分配任何管理数据，这对于更一般的调用通常是必需的，例如，

let baz x = 
  1 + foo x (* foo is not in the tail position! *)

在这个例子中，我们看到 <...> + <...> 是最后一个表达式，所以计算机需要计算 + 的两边并将它们存储在内存中的某个地方，然后才能最终求和他们起来。这个“内存中的某个地方”通常是堆栈，它是大多数现代操作系统上的稀缺资源。如果我们迭代地进行此类调用，则堆栈的稀缺性变得尤为重要。

最后，如果尾调用是递归的，则称为 tail-recursive 调用。 Tail-recursive 调用在迭代过程的实现中非常有效，而不是依赖专门的 ad-hoc control-flow 结构，如 for 和 while，我们可以表达以更清晰的方式重复过程，例如，

let rec contains_element k = function
  | [] -> false
  | x :: _ when k = x -> true
  | _ :: xs -> contains_element k xs

自然地描述了一个列表包含一个元素k，如果它的头部是k或者如果列表的尾部包含元素k。该算法也很好地展示了 above-specified 规则的例外情况，即尾调用必须是函数中的最后一次调用，

(* this version is also tail recursive! *)
let rec contains_element k = function
  | [] -> false
  | x :: xs -> x = k || contains_elements xs

这是因为 OCaml 将 short-circuit 运算符 ¹ 的 right-hand 端的调用视为尾调用，因为您不需要在应用运算符之前计算两个操作数。

¹⁾ OCaml中的||和&&分别代表逻辑析取（OR）和合取（AND）。

Answer 2

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

每次调用函数时，都会创建一个堆栈帧，其中包含函数完成其工作所需的数据。当它完成时，它的 return 值被 returned“向上”堆栈到它的调用者。

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

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

很简单。一个空列表的总和当然是0。 non-empty 列表的总和是第一个元素加上列表其余部分的总和。

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

如果我们用一个小列表来做这件事，那真的不是问题。堆栈是有限的，但还不足以成为一个问题。

但是如果我们尝试使用一个包含多个元素的列表，我们将运行出栈 space 并得到一个错误。

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

为此，我们使用累加器，通常称为 acc。

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

随着 tail_sum 遍历列表，它会保持总和的运行ning 累积。当列表为空时，它 return 就是那个累加器。我们只需要始终使用 0.

的起始累加器调用 tail_sum

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 中更直接的方法是可能的，因为有关最终收件人的信息在每个阶段都会传递。同样的目的达到了，只是这一次一旦出了每个人的手，他们就可以忘记了。他们不再是实现目标所必需的。

Can someone explain OCaml Tail Recursion Like I am five?