Course Builder个人学习工作台 · 本地模式
OCaml：从类型推导到可测试的命令行工具

06 · 列表与递归：沿着数据结构求解

目标：用列表模式匹配编写递归求和，并将它改成使用累加器的尾递归。

OCaml 的列表是不可变链表：要么为空 []，要么是一个头元素和一条尾列表 x :: rest。[25; 35; 10] 是整数列表，同一列表内的元素类型必须一致。列表使用分号分隔，元组使用逗号；[25, 35] 是包含一个二元组的列表，并非两个整数。

先暂时放下 Go slice、Python list、JS array 带来的下标遍历习惯。OCaml list 的拆解入口是“头和尾”：x :: rest 里的 rest 就是现有尾列表，不需要把余下元素逐个复制出来。后面的累加器则可以借用你熟悉的循环变量来理解：每次递归调用把下一轮的状态作为参数传入，而不是修改上一轮的变量。

递归函数的结构可以跟着数据结构走：空列表直接给答案；非空列表处理头元素，再递归处理更短的尾列表。let rec 允许函数体引用自己。每次递归都必须向终止情况推进，否则类型正确也可能永远跑不完。

实验：把“剩余工作”变成一个参数

创建 recursion.ml：

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

let sum_tail xs =
  let rec loop acc remaining =
    match remaining with
    | [] -> acc
    | x :: rest -> loop (acc + x) rest
  in
  loop 0 xs

let () =
  let minutes = [25; 35; 10] in
  Printf.printf "sum=%d tail=%d empty=%d\n"
    (sum minutes) (sum_tail minutes) (sum_tail [])

先在纸上展开 sum [25; 35]，再运行：

ocaml recursion.ml

预期输出：

sum=70 tail=70 empty=0

普通版本先得到 sum [35] 才能执行 25 + ...，调用者还有待完成的加法。尾递归版本先更新 acc，最后一步直接调用 loop，返回后没有额外工作。其状态依次是 (0, [25;35;10])、(25, [35;10])、(60, [10])、(70, [])。

这个简单尾调用可以复用调用栈空间；不意味着程序完全不分配内存，也不意味着所有带 rec 的函数都是尾递归。这里两个算法都遍历一次列表，时间随元素数线性增长。列表前插 :: 很适合逐步建立结果；反复在尾部用 @ 追加会重复遍历左侧。

从求和迁移到计数

  1. 将输入改为空列表，两个实现都应返回 0。
  2. 将输入改成 [25; -5]，两者都返回 20。这是通用求和，不负责判断时长是否合法。
  3. 恢复主示例；不要把验证规则塞进每个集合算法。

独立练习：编写尾递归的 count_positive，只统计大于零的元素数量。[-2; 0; 25; 35] 应为 2，空列表应为 0。思考：累加器保存的是分钟数还是记录数？

参考实现

追加到主文件并运行：

let count_positive xs =
  let rec loop count remaining =
    match remaining with
    | [] -> count
    | x :: rest ->
        let next = if x > 0 then count + 1 else count in
        loop next rest
  in
  loop 0 xs

let () =
  assert (count_positive [-2; 0; 25; 35] = 2);
  assert (count_positive [] = 0);
  print_endline "recursion checks passed"

累加器是“已经看过的正数个数”。记录其含义是检查递归正确性的好办法：每处理一个新元素，这个解释都应该继续成立。

若出现 Unbound value sum，检查递归定义是否有 rec。若程序不结束，检查递归参数有没有从 xs 变为 rest。若只在大输入上出现栈问题，寻找递归调用之后是否还剩计算；不要仅增加栈限制。空列表必须作为明确的基本情况处理。

参考资料