OCaml 教程 / 递归函数
递归函数
概述
递归是函数式编程的核心技术。在 OCaml 中，由于默认不可变性，递归取代了命令式语言中的循环。理解递归和尾调用优化（TCO）是写出高效 OCaml 代码的关键。
递归基础
递归函数通过调用自身来解决问题。每个递归函数需要：
- 基准情况（Base Case）：不再递归的终止条件
- 递归情况（Recursive Case）：将问题分解为更小的子问题
(* 阶乘：n! = n * (n-1)! *)
let rec factorial n =
if n <= 1 then 1 (* 基准情况 *)
else n * factorial (n - 1) (* 递归情况 *)
let _ = factorial 5 (* => 120 *)
let _ = factorial 0 (* => 1 *)
(* 用 match 重写 *)
let rec factorial n =
match n with
| 0 | 1 -> 1
| n -> n * factorial (n - 1)
(* 斐波那契 *)
let rec fib n =
match n with
| 0 -> 0
| 1 -> 1
| n -> fib (n - 1) + fib (n - 2)
let _ = fib 10 (* => 55 *)
⚠️ 注意：上面的 fib 实现效率很差（指数时间复杂度），每次调用都会产生两个递归调用。实际使用时应采用尾递归版本或记忆化。
尾递归（Tail Recursion）
尾递归是指递归调用是函数的最后一个操作。尾递归函数可以被编译器优化为循环（尾调用优化，TCO），避免栈溢出。
(* 非尾递归版本 — n 最后还需要乘法 *)
let rec factorial n =
if n <= 1 then 1
else n * factorial (n - 1) (* 递归调用后还有 * n 操作 *)
(* 尾递归版本 — 使用累加器 *)
let factorial n =
let rec aux n acc =
if n <= 1 then acc
else aux (n - 1) (n * acc) (* 递归调用是最后一步 *)
in
aux n 1
let _ = factorial 5 (* => 120 *)
判断尾递归
(* ✅ 尾递归：递归调用在尾部位置 *)
let rec sum acc lst =
match lst with
| [] -> acc
| x :: rest -> sum (acc + x) rest (* 尾调用 *)
(* ❌ 非尾递归：递归调用后还有操作 *)
let rec sum lst =
match lst with
| [] -> 0
| x :: rest -> x + sum rest (* 尾调用后还有 + x *)
(* ⚠️ 隐式非尾递归 *)
let rec f n =
let _ = print_int n in (* 这不是问题 *)
if n <= 0 then 0
else f (n - 1) (* 这是尾调用 *)
let rec g n =
let result = g (n - 1) in (* 不是尾调用，结果绑定到变量 *)
result + 1
💡 提示：一个简单的方法判断是否为尾递归——看递归调用的返回值是否直接就是整个函数的返回值。
尾调用优化（TCO）
OCaml 的 TCO 行为
OCaml 编译器保证对尾调用进行优化：
(* 尾递归：不会栈溢出 *)
let count_to n =
let rec aux i acc =
if i > n then acc
else aux (i + 1) (acc + 1)
in
aux 0 0
let _ = count_to 10_000_000 (* => 10000000，正常运行 *)
(* 非尾递归：会栈溢出 *)
let rec count_bad n i =
if i > n then 0
else 1 + count_bad n (i + 1) (* 不是尾调用 *)
(* let _ = count_bad 10_000_000 0 ← 可能导致 Stack_overflow *)
栈溢出的处理
(* 捕获栈溢出异常 *)
let safe_count n =
try
Some (count_bad n 0)
with
| Stack_overflow -> None
⚠️ 注意：OCaml 默认栈大小约为 1MB。对于深度递归（> 10 万层），务必使用尾递归。可通过 OCAMLRUNPARAM 环境变量调整栈大小。
累加器技术
将非尾递归转换为尾递归的通用方法是使用累加器（Accumulator）：
列表求和
(* 非尾递归 *)
let rec sum = function
| [] -> 0
| x :: rest -> x + sum rest
(* 尾递归 + 累加器 *)
let sum lst =
let rec aux acc = function
| [] -> acc
| x :: rest -> aux (acc + x) rest
in
aux 0 lst
列表反转
(* 尾递归反转列表 *)
let rev lst =
let rec aux acc = function
| [] -> acc
| x :: rest -> aux (x :: acc) rest
in
aux [] lst
let _ = rev [1; 2; 3; 4; 5] (* => [5; 4; 3; 2; 1] *)
Map 函数
(* 非尾递归 map *)
let rec map f = function
| [] -> []
| x :: rest -> f x :: map f rest
(* 尾递归 map（注意结果是反转的，需要再反转） *)
let map f lst =
let rec aux acc = function
| [] -> List.rev acc
| x :: rest -> aux (f x :: acc) rest
in
aux [] lst
Filter 函数
let filter pred lst =
let rec aux acc = function
| [] -> List.rev acc
| x :: rest ->
if pred x then aux (x :: acc) rest
else aux acc rest
in
aux [] lst
let _ = filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6]
(* => [2; 4; 6] *)
Fold 函数
(* fold_left 天然就是尾递归 *)
let rec fold_left f acc = function
| [] -> acc
| x :: rest -> fold_left f (f acc x) rest
(* fold_right 不是尾递归 *)
let rec fold_right f lst acc =
match lst with
| [] -> acc
| x :: rest -> f x (fold_right f rest acc)
(* fold_right 的尾递归版本 *)
let fold_right f lst acc =
let reversed = List.rev lst in
fold_left (fun acc x -> f x acc) acc reversed
互递归（Mutual Recursion）
两个或多个函数相互调用：
(* 经典示例：奇偶判断 *)
let rec is_even = function
| 0 -> true
| n -> is_odd (n - 1)
and is_odd = function
| 0 -> false
| n -> is_even (n - 1)
(* 有限状态机 *)
type state = A | B | C | Accept | Reject
let rec state_a = function
| [] -> false
| '0' :: rest -> state_b rest
| '1' :: rest -> state_a rest
| _ -> false
and state_b = function
| [] -> false
| '0' :: rest -> state_a rest
| '1' :: rest -> state_c rest
| _ -> false
and state_c = function
| [] -> true (* 接受状态 *)
| '0' :: rest -> state_b rest
| '1' :: rest -> state_a rest
| _ -> false
(* 接受包含 "01" 子序列的二进制字符串 *)
let accepts s =
let chars = List.init (String.length s) (String.get s) in
state_a chars
let _ = accepts "1101" (* => true *)
let _ = accepts "111" (* => false *)
⚠️ 注意：相互递归的函数必须用 let rec ... and ... 定义在同一个 let rec 块中。普通的 let 不能引用下方的绑定。
递归数据结构
链表
(* OCaml 列表本身就是递归定义的 *)
type 'a my_list =
| Empty
| Cons of 'a * 'a my_list
let rec length = function
| Empty -> 0
| Cons (_, rest) -> 1 + length rest
let rec to_list = function
| Empty -> []
| Cons (x, rest) -> x :: to_list rest
let rec from_list = function
| [] -> Empty
| x :: rest -> Cons (x, from_list rest)
二叉树
type 'a tree =
| Leaf
| Node of 'a tree * 'a * 'a tree
(* 创建示例树 *)
let sample_tree =
Node (
Node (Leaf, 1, Leaf),
2,
Node (Node (Leaf, 3, Leaf), 4, Leaf)
)
(* 计算树的大小 *)
let rec size = function
| Leaf -> 0
| Node (left, _, right) -> 1 + size left + size right
(* 计算树的高度 *)
let rec height = function
| Leaf -> 0
| Node (left, _, right) -> 1 + max (height left) (height right)
(* 中序遍历 *)
let rec inorder = function
| Leaf -> []
| Node (left, v, right) ->
inorder left @ [v] @ inorder right
(* 尾递归中序遍历（使用累加器） *)
let inorder tree =
let rec aux acc = function
| Leaf -> acc
| Node (left, v, right) ->
aux (v :: aux acc right) left
in
List.rev (aux [] tree)
let _ = size sample_tree (* => 4 *)
let _ = height sample_tree (* => 3 *)
let _ = inorder sample_tree (* => [1; 2; 3; 4] *)
(* 在 BST 中查找 *)
let rec search x = function
| Leaf -> false
| Node (left, v, right) ->
if x = v then true
else if x < v then search x left
else search x right
(* BST 插入 *)
let rec insert x = function
| Leaf -> Node (Leaf, x, Leaf)
| Node (left, v, right) ->
if x = v then Node (left, v, right)
else if x < v then Node (insert x left, v, right)
else Node (left, v, insert x right)
💡 提示：递归数据结构是 OCaml 的强项。ADT + 模式匹配 + 递归函数的组合非常优雅。
递归与迭代对比
虽然 OCaml 以递归为主，但也可以使用命令式循环：
(* while 循环 *)
let sum_while lst =
let total = ref 0 in
let remaining = ref lst in
while !remaining <> [] do
match !remaining with
| x :: rest ->
total := !total + x;
remaining := rest
| [] -> ()
done;
!total
(* for 循环 *)
let factorial_for n =
let result = ref 1 in
for i = 2 to n do
result := !result * i
done;
!result
(* 等价的尾递归版本 *)
let factorial_tail n =
let rec aux i acc =
if i > n then acc
else aux (i + 1) (acc * i)
in
aux 1 1
| 特性 | 递归 | 命令式循环 |
|---|---|---|
| 可变状态 | 不需要 | 需要 ref 或 Array |
| 栈安全 | 需尾递归 | 天然栈安全 |
| 代码风格 | 声明式 | 命令式 |
| 性能 | TCO 后等同 | 直接 |
| 推荐度 | ⭐⭐⭐⭐⭐ | 仅在必要时使用 |
分治策略
(* 归并排序 — 分治经典 *)
let rec merge_sort lst =
match lst with
| [] | [_] -> lst
| _ ->
let mid = List.length lst / 2 in
let left = List.filteri (fun i _ -> i < mid) lst in
let right = List.filteri (fun i _ -> i >= mid) lst in
merge (merge_sort left) (merge_sort right)
and merge left right =
match left, right with
| [], r -> r
| l, [] -> l
| x :: xs, y :: ys ->
if x <= y then x :: merge xs right
else y :: merge left ys
(* 快速排序 *)
let rec quicksort = function
| [] | [_] as lst -> lst
| pivot :: rest ->
let left = List.filter (fun x -> x < pivot) rest in
let equal = List.filter (fun x -> x = pivot) rest in
let right = List.filter (fun x -> x > pivot) rest in
quicksort left @ (pivot :: equal) @ quicksort right
let _ = quicksort [3; 1; 4; 1; 5; 9; 2; 6]
(* => [1; 1; 2; 3; 4; 5; 6; 9] *)
递归调试技巧
打印追踪
let rec factorial_debug indent n =
let prefix = String.make indent ' ' in
Printf.printf "%sfactorial(%d)\n" prefix n;
if n <= 1 then begin
Printf.printf "%s返回 1\n" prefix;
1
end else begin
let result = n * factorial_debug (indent + 2) (n - 1) in
Printf.printf "%s返回 %d\n" prefix result;
result
end
let _ = factorial_debug 0 5
(* 输出:
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
返回 1
返回 2
返回 6
返回 24
返回 120
*)
使用 trace 工具
# 使用 OCaml 的 tracing 工具
opam install ocaml-trace
断言检查
let rec safe_factorial n =
assert (n >= 0); (* 确保输入合法 *)
if n <= 1 then 1
else n * safe_factorial (n - 1)
业务场景
| 场景 | 递归技术 |
|---|---|
| 文件系统遍历 | 树递归 |
| JSON 解析 | 变体递归 + 模式匹配 |
| 数学计算 | 累加器 + 尾递归 |
| 编译器 | AST 遍历 |
| 图算法 | 带 visited 集合的递归 |
| 状态机 | 互递归 |