OCaml 中二叉树的尾递归最大元素

Question

我正在练习尾递归，并且考虑到类型

type 'a tree = Leaf of 'a | Pair of 'a tree * 'a tree

以及一个查找二叉树中最大元素的函数

let rec tree_max t = match t with 
    | Leaf v -> v 
    | Pair (l,r) -> max (tree_max l) (tree_max r)

使上述函数尾递归

---

我努力了

let rec tree_max t acc= match t with 
    | Leaf v -> acc
    | Pair (l,r) -> (max (tree_max l) (tree_max r))::ACC

我也尝试过

let rec tree_max t acc= match t with 
    | Leaf v -> acc
    | Pair (l,r) -> if (max (tree_max l) (tree_max l) = acc) then tree_max l acc else tree_max r acc

但它们都会产生语法错误。有谁知道如何实现这个？

Answer 1

TL;博士; 这个问题比看起来要深一些，因为我不想给别人做作业，所以我决定写一个关于将递归函数变成尾递归函数的指南。它比我预期的要大一点:)

（尾）递归的终极指南

什么是尾递归？

识别函数何时是尾递归、何时不是尾递归并不总是那么容易。关键思想是，如果您在递归调用后做了一些工作，那么您的函数就不是尾递归的。而要使其成为尾递归，我们需要向递归调用传递足够的信息，以便后者无需我们干预即可计算出结果，即函数的结果成为递归调用的结果。

length这是一个简单的例子，一个计算列表长度的非尾递归函数，

let rec length = function
  | [] -> 0
  | _ :: xs -> 1 + length xs

我们可以看到，1 + length xs计算机首先进行计算length xs，然后等待其结果，然后将其加一。显然，我们可以将当前长度传递给递归调用并让基本情况返回它，例如，

let rec length acc = function
  | [] -> acc
  | _ :: xs -> length (acc+1) xs

因此，正如您所看到的，技巧是使用参数将信息传递到递归中。需要立即注意的是，我们现在有一个额外的参数，acc（代表accumulator）。约定是在嵌套函数中向界面的最终用户隐藏此参数。我通常称这个函数为loop，例如

let length xs = 
  let rec loop acc = function
    | [] -> acc
    | _ :: xs -> loop (acc+1) xs in
  loop 0 xs

在length示例中，我们能够将算法从内存大小的 O(N) 改进到 O(1)。事实上，在非尾递归版本中，编译器创建了一个等于列表长度的堆栈调用链，每个槽存储子列表的长度。本质上，编译器构建了一个立即结果的单链接列表，然后使用+运算符对其进行缩减。这是一种非常低效的求和方法n。

但有时，我们无法将递归参数减少为单个标量值，因此在堆栈中构建结果可能是有益的，考虑将函数map应用于列表的每个元素并构建新的结果列表的函数，

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

没有办法减少这个函数，O(N)因为O(1)我们必须构建并返回一个新的地图。但它会消耗堆栈，这是一种稀缺^资源，与常规的堆内存不同。那么让我们把这个函数变成尾递归函数。同样，我们必须在递归中传递必要的信息，以便当我们到达递归底部时我们可以构建答案，

let map f xs =
  let rec loop acc = function
    | [] -> List.rev acc
    | x :: xs -> loop (x::acc) xs in
  loop [] xs

正如您所看到的，我们再次使用了嵌套循环函数的技巧acc来隐藏额外的参数。与前面的示例不同，我们使用列表而不是整数来累积结果。由于我们假装列出了列表，因此我们最终得到了相反顺序的结果，因此我们必须将其反转回底部。我们可以改为追加到列表中，但这会导致代码效率非常低，因为追加到单链表是一个O(N)操作，因此如果我们重复N多次，就会变得O(N^2)复杂。

树上的递归

在上面的例子中，我们对累加器有或多或少明显的选择，但是树状结构呢？对于树，我们必须在每个步骤上递归几次，例如，

let max_elt t = 
  let rec loop current_max t = match t with
    | Leaf x -> max current_max x (* so far so good *)
    | Tree (l,r) -> <??> in
  loop <??> t

正如我们所看到的，将函数转换为累加器式递归，并明显选择累加器，因为整数没有帮助。首先，我们现在必须对初始最大值做出可疑的选择，接下来，这是主要问题是我们必须分支l，r并且我们不能在同一个递归调用中递归到它们两个。 .或者我们可以吗？

是的，我们可以，而且事实上，有多种解决方案。让我们从累加器式递归开始。由于我们想要在几个子树上递归（在我们的例子中是两个子树）并且我们想要在一次调用中完成它，所以我们必须将树的另一个分支传递到累加器中。因此累加器本身就变成了我们尚未访问过的树的列表。这种方法的通用名称是“工作列表算法”，其关键思想是我们做尽可能多的工作，并将其余的工作推入工作列表，例如，

let max_elt t =
  let rec loop work t =
    match t with
    | Tree (l,r) -> loop (l::work) r
    | Leaf x -> match work with
      | [] -> x
      | [Leaf x'] -> max x x'
      | Tree _ as t' :: ts -> loop (t::ts) t'
      | Leaf x' :: t :: ts -> loop (Leaf (max x x') :: ts) t in
  loop [] t

哎呀，这看起来很复杂，比原来的堆栈消耗版本复杂得多。这是否值得，即我们是否显着提高了我们的表现？对于平衡树，不，我们是平等的 - 基于堆栈的版本消耗O(depth(t))堆栈槽，其中depth是树的深度。由于平衡二叉树的大小N（节点数）2^depth(t)实际上是我们消耗的O(log(N))，这很好。我们的尾递归版本也消耗相同数量的堆。对于平衡树，我们不应该害怕消耗堆栈内存，因为在此之前我们将耗尽堆内存（同样，要存储深度为 N 的树，我们需要 2^N 个元素，即使堆栈是由于有限的 64 个槽位，我们将能够处理大至 2^64 的树，这比任何计算机所能容纳的要大得多）。这就是为什么对于平衡树我们不需要担心尾递归并安全地使用正则递归，这更具可读性和效率。

但如果树不平衡怎么办？即，当我们仅在左侧有子树而在右侧有叶子时。在这种极端情况下，我们的元素数量等于列表的深度。不幸的是，除非我们专门平衡我们的树（这是另一个有趣的主题），否则我们经常会遇到这样的树，即，尝试编写一个of_list从列表生成树的函数，很有可能您最终会得到一个不平衡列表。

对于不平衡的树，我们很容易出现堆栈溢出。但是上面这个函数，很难理解，也很难证明它终止了。

也许有一种方法可以使其尾递归且易于理解？答案是肯定的，所以请继续阅读。

树上的递归（不涉及大脑）

好吧，下一个技巧有点难以掌握，因为它涉及到延续。如果你阻止你的大脑尝试理解这个概念，那么这将是一个无需动脑筋的练习，仅仅是一种技术替代。但我们并不是在寻找简单的道路，所以让我们的大脑做一些工作。

关键思想仍然相同，我们需要调用递归函数一次并向其传递递归完成工作所需的一些值。在前面的示例中，我们将“要完成的工作”具体化为尚未处理的节点列表。但是，如果我们将其表示为一个函数，该函数将接收中间结果并继续工作，即作为延续。惯例是调用延续k，但我们将调用它return，

let max_elt t =
  let rec loop t return =
    match t with
    | Leaf x -> return x
    | Tree (l,r) ->
      loop l @@ fun x ->
      loop r @@ fun y ->
      return (max x y) in
  loop t (fun x -> x)

好的，首先，什么是@@我们调用两次循环？这是一个应用程序运算符，定义为let (@@) f x = f x，因此如果我们重写我们的loop函数，我们可以看到我们确实每次调用都会调用它一次，

let rec loop t return =
    match t with
    | Leaf x -> return x
    | Tree (l,r) ->
      loop l (fun x ->
          loop r (fun y ->
              return (max x y)))

因此，慢慢地，在这种Tree (l,r)情况下，我们调用loop l <cont1>并向其传递一个延续（函数），该延续（函数）接收子树的最大值，l然后调用loop r <cont2>，它从 接收最大值r，将它们组合起来找到两个中的最大值，然后使用继续return将其发送回（向上）。

仍然不能完全确定这是尾递归吗？让我们尝试将其重写得更详细，

  let rec loop t return =
    match t with
    | Leaf x -> return x
    | Tree (l,r) ->
      let cont1 x =
        let cont2 y = return (max x y) in
        loop r cont2 in
      loop l cont1

正如您所看到的，对循环的所有调用都位于尾部位置。但它是如何运作的呢？

这里的大思想是每个延续捕获一些信息，即在每个延续中我们都有一些从外部范围捕获的自由变量，例如cont1捕获正确的树r，并cont2捕获上层延续return，所以最后我们有一个延续的链接列表。因此，没有免费的奶酪，我们仍然使用O(N)内存插槽，但由于延续存储在堆内存中，我们不再浪费宝贵的堆栈。

好的，现在是最后一步，我们如何应用这种技术而不会给我们的大脑带来过大的压力，即纯粹的句法？为此，我们将使用 OCaml 的新功能，称为绑定运算符，它允许我们定义自己的letXX运算符，例如，

let (let@) = (@@)

因此f (fun x -> <body>)可以表示为let@ x = f in <body>并使用此运算符，我们可以将尾递归版本表示为与非尾递归版本几乎相同，

let max_elt t =
  let rec loop t return =
    match t with
    | Leaf x -> return x
    | Tree (l,r) ->
      let@ x = loop l in
      let@ y = loop r in
      return (max x y) in
  loop t (fun x -> x)

与非尾递归版本相比，

let rec max_elt t =
  match t with
  | Leaf x -> x
  | Tree (l,r) ->
    let x = max_elt l in
    let y = max_elt r in
    max x y

所以我们可以构建一个简单的语法规则，

0. 将额外的函数参数附加到参数列表
1. 所有递归调用都应与let@
2. 返回值应通过 传递return，除非我们想提前逃离递归。

早期逃逸或短路

如果我们不使用return在递归中向上传递值怎么办？在这种情况下，我们的结果立即成为整个顶级调用的结果，因此我们可以在找到元素时缩短搜索，而不检查其他元素。例如，以下是我们如何测试树的元素成员资格，

let has t needle =
  let rec loop t return = match t with
    | Leaf x -> x = needle || return ()
    | Tree (l,r) ->
      let@ () = loop l in
      loop r return in
  loop t (fun () -> false)

您可以看到，let@ () = loop l我们甚至懒得从子树搜索中返回 true 或 false。我们仅使用函数返回给我们的事实作为该元素不存在于左子树中的证据，因此我们需要检查右子树。

延续是函数式语言的一个非常强大的功能，你可以用它们实现奇妙的东西，比如可变参数函数、非确定性计算、轻松表达回溯等等。但这是一个不同的话题，我希望我们最终能够探讨这个话题。

^1）是否稀缺取决于架构、操作系统及其配置。在现代Linux上，您可以通过设置使堆栈大小不受限制，并且根本不用担心堆栈溢出ulimit -s unlimited。在其他操作系统上，最大堆栈大小有硬性限制。