PHP递归计算组合数：递归求解组合数学问题的方法
组合数是组合数学中最基础的概念之一，表示从n个元素中选取k个元素的组合方式数量，通常记作C(n,k)或C_n^k。在实际开发中，我们可能需要通过编程快速计算组合数，而递归是一种符合组合数学定义、逻辑直观的实现方式。本文将介绍如何使用PHP通过递归方法计算组合数，同时解析递归逻辑的实现细节。
组合数的递归定义
组合数的递归性质来源于组合数学的递推公式：
- 当k=0或k=n时，C(n,k)=1，这是递归的终止条件
- 当0<k<n时，C(n,k) = C(n-1,k-1) + C(n-1,k)，含义是是否选取第n个元素，选取则从第n-1个元素中选k-1个，不选取则从第n-1个元素中选k个
根据这个递推关系，我们可以很自然地写出递归计算的代码逻辑。
PHP递归实现组合数计算
下面是一个标准的PHP递归计算组合数的函数实现，代码中包含了基础的逻辑判断和递归调用：
<?php
/**
* 递归计算组合数C(n,k)
* @param int $n 总元素个数
* @param int $k 选取的元素个数
* @return int 组合数结果
*/
function combination(int $n, int $k): int {
// 输入合法性校验：k不能小于0，也不能大于n
if ($k < 0 || $k > $n) {
return 0;
}
// 递归终止条件：k=0或者k=n时，组合数为1
if ($k == 0 || $k == $n) {
return 1;
}
// 递归调用递推公式：C(n,k) = C(n-1,k-1) + C(n-1,k)
return combination($n - 1, $k - 1) + combination($n - 1, $k);
}
// 测试示例：计算C(5,2)，结果为10
$n = 5;
$k = 2;
$result = combination($n, $k);
echo "C({$n},{$k}) = {$result}"; // 输出：C(5,2) = 10
?>代码中的combination函数首先做了输入合法性校验，避免传入无效的参数导致错误结果。接着判断递归终止条件，当选取数量k为0或者等于总数量n时，只有1种组合方式，直接返回1。否则按照递推公式拆分问题，分别递归计算两个子问题的结果再求和。
递归实现的优化说明
上面的基础递归实现虽然逻辑清晰，但存在重复计算的问题，比如计算C(5,2)时会重复计算C(3,1)等子问题，当n较大时性能会明显下降。我们可以通过记忆化递归的方式优化，将已经计算过的结果缓存起来，避免重复计算：
<?php
// 记忆化数组，缓存已经计算过的组合数结果
$memo = [];
/**
* 记忆化递归计算组合数
* @param int $n 总元素个数
* @param int $k 选取的元素个数
* @return int 组合数结果
*/
function combinationMemo(int $n, int $k): int {
global $memo;
// 输入合法性校验
if ($k < 0 || $k > $n) {
return 0;
}
// 递归终止条件
if ($k == 0 || $k == $n) {
return 1;
}
// 构造缓存键，避免不同n,k组合冲突
$key = $n . '_' . $k;
// 如果已经计算过，直接返回缓存结果
if (isset($memo[$key])) {
return $memo[$key];
}
// 递归计算并缓存结果
$memo[$key] = combinationMemo($n - 1, $k - 1) + combinationMemo($n - 1, $k);
return $memo[$key];
}
// 测试优化后的函数
$n = 10;
$k = 3;
$result = combinationMemo($n, $k);
echo "C({$n},{$k}) = {$result}"; // 输出：C(10,3) = 120
?>优化后的版本通过$memo数组缓存了已经计算过的子问题结果，每次计算前先检查缓存，大大减少了递归调用的次数，提升了计算效率。
使用场景与注意事项
递归计算组合数的方式适合n值较小的场景，因为组合数的增长速度非常快，当n超过20时，即使使用记忆化优化，也可能超出PHP整数类型的存储范围，此时可以考虑使用大数扩展或者改用阶乘公式计算（需要注意阶乘溢出的问题）。
另外，如果需要频繁计算大量组合数，建议预先计算并存储常用范围的组合数结果，避免重复计算，进一步提升程序运行效率。