OCaml实现组合数函数遇异常：阶乘溢出与除零错误求助

你的问题和递归完全无关，核心是OCaml原生int类型的整数溢出，以及组合数计算方式的效率问题，具体拆解如下：

1. 为什么会出现负数和除零异常？ #

OCaml的int是固定精度整数（多数系统为32位，范围是-2^31到2^31-1）：

• 当计算fact 22时，22!的实际值远大于2^31-1，触发整数溢出，数值回绕成负数，这就是你看到“超大负数”的原因。
• 计算更大的数（比如66）时，阶乘溢出后会进一步回绕，甚至变成0。比如fact 64或fact 66溢出后结果为0，此时comb (66,2)中的除法就会出现除数为0，触发异常。

尾递归只是解决递归调用的栈溢出问题，和整数溢出没有任何关系，所以你改尾递归后问题依然存在。

2. 修复方案 #

方案一：优化组合数计算逻辑（避免大阶乘） #

组合数公式可以变形，避免直接计算超大阶乘，从而减少溢出概率：

let comb (m, n) =
  let n = min n (m - n) in  (* 利用C(m,n)=C(m,m-n)减少计算量 *)
  let rec calc num_acc den_acc i =
    if i > n then num_acc / den_acc
    else calc (num_acc * (m - n + i)) (den_acc * i) (i + 1)
  in
  calc 1 1 1

这种方式通过逐步乘分子分母，计算过程中数值小很多，comb (66,2)会直接计算66*65/(2*1)，不会触发溢出和除零。

方案二：使用任意精度大整数 #

如果需要处理更大的m和n，直接用OCaml的原生int不够，推荐用Zarith库（任意精度整数）：
先安装库：

opam install zarith

修改代码：

open Z

let rec fact num =
  let rec help n acc =
    if n > zero then help (n - one) (acc * n)
    else acc
  in
  help num one

let comb (m, n) =
  fact (of_int m) / fact (of_int (m - n)) / fact (of_int n)

这个方案完全不会有溢出问题，能处理任意大的组合数计算。

方案三：改用64位整数 #

如果你的环境支持，可以用int64类型，它的范围更大（-2^63到2^63-1），能处理更大的阶乘：

let rec fact num =
  let rec help n acc =
    if Int64.gt n Int64.zero then help (Int64.sub n Int64.one) (Int64.mul acc n)
    else acc
  in
  help num Int64.one

let comb (m, n) =
  let m' = Int64.of_int m in
  let n' = Int64.of_int n in
  Int64.div (Int64.div (fact m') (fact (Int64.sub m' n'))) (fact n')

但这种方式依然有上限，超过2^63-1还是会溢出。

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