OCaml尾递归实现二叉树最大元素查找函数问询

你现有代码的错误原因 #

第一个版本问题 #

• OCaml 标识符大小写敏感，你定义的累加参数是acc，但代码里写的ACC是未声明的变量，直接触发语法错误
• 你声明的tree_max需要传入t和acc两个参数，但递归调用时只写了tree_max l/tree_max r，参数数量不匹配
• 逻辑完全不符合要求：你用了列表拼接符::，返回值变成了列表类型，和要求返回的树元素类型不符；且你先递归计算左右子树再做计算，递归调用不是函数的最后一步，本质还是非尾递归，达不到优化效果

第二个版本问题 #

• 同样存在递归调用参数数量不匹配的语法错误
• 逻辑错误：代码里两次调用tree_max l，完全没有处理右子树r，就算语法修正也无法算出正确最大值
• 递归调用后还要做条件判断，依然不是尾递归

正确尾递归实现 #

尾递归的核心要求是递归调用必须是函数的最后一个操作，调用后不能有任何额外计算。二叉树尾递归遍历的通用方案是用手动维护的栈替代运行时的调用栈，所有计算都在递归前完成。

完整代码 #

(* 给定的树类型定义 *)
type 'a tree = Leaf of 'a | Pair of 'a tree * 'a tree

(* 尾递归版本树最大值函数 *)
let tree_max_tailrec t =
  (* 辅助函数：stack是待遍历的树节点栈，current_max是当前找到的最大值（用option兼容泛型场景） *)
  let rec aux stack current_max =
    match stack with
    | [] -> 
      (match current_max with
       | Some v -> v
       | None -> failwith "空树无最大值") (* 原实现默认树非空，此处仅为兜底 *)
    | (Leaf v) :: rest_stack ->
      (* 碰到叶子节点，更新当前最大值后继续处理栈剩余节点 *)
      let new_max = match current_max with
        | None -> v
        | Some m -> max v m
      in
      aux rest_stack (Some new_max)
    | (Pair (left, right)) :: rest_stack ->
      (* 碰到内部节点，把左右子树压入栈后继续处理 *)
      aux (left :: right :: rest_stack) current_max
  in
  (* 入口：把根节点压入栈，初始最大值设为None *)
  aux [t] None

验证示例 #

(* 测试用树：Pair(Pair(Leaf 1, Leaf 5), Pair(Leaf 3, Leaf 2)) 最大值为5 *)
let test_tree = Pair(Pair(Leaf 1, Leaf 5), Pair(Leaf 3, Leaf 2))
let () = print_int (tree_max_tailrec test_tree) (* 输出5 *)

内容的提问来源于stack exchange，提问作者hexaquark