如何将Java普通递归二项式系数函数改写为尾递归实现？

原普通递归代码 #

你给出的普通递归版本如下，它通过分拆为两个子问题相加实现，但由于最后一步是加法操作而非单一递归调用，无法被优化为尾递归：

public static long binomCoeffRecursive(int n, int k) {
    if (n == k) {
        return 1;
    }
    if (k > n) {
        return 0;
    }
    if (k == 0) {
        return 1;
    }
    return binomCoeffRecursive(n-1, k-1) + binomCoeffRecursive(n - 1, k);
}

尾递归转换核心思路 #

尾递归的关键是将中间计算结果通过参数传递，让递归调用成为函数的最后执行操作，这样编译器可以复用当前栈帧，避免栈溢出。对于二项式系数，我们可以利用组合数的递推公式：
$$C(n,k) = C(n,k-1) \times \frac{n - k + 1}{k}$$
同时结合组合数的对称性 $C(n,k)=C(n,n-k)$（取较小的k减少计算次数），用累加器保存当前计算结果，逐步递归到终止条件。

具体转换步骤 #

• 预处理边界条件：先处理k>n返回0，k=0或k=n返回1；同时将k替换为min(k, n-k)，减少递归次数。
• 引入辅助尾递归函数：新增参数acc（累加器），用于保存当前已计算的乘积结果，初始值为1。
• 定义递归终止条件：当k=0时，直接返回累加器acc。
• 尾递归调用逻辑：每次递归时，更新累加器为acc * (n - k + 1) / k，同时将k减1，递归调用辅助函数。

尾递归实现代码 #

public static long binomCoeffTailRecursive(int n, int k) {
    // 处理边界条件
    if (k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    // 利用对称性减少计算量
    k = Math.min(k, n - k);
    // 调用辅助尾递归函数，初始累加器为1
    return binomCoeffTailHelper(n, k, 1);
}

// 尾递归辅助函数
private static long binomCoeffTailHelper(int n, int k, long acc) {
    // 终止条件：k减到0时返回累加结果
    if (k == 0) {
        return acc;
    }
    // 尾递归调用：更新累加器，k减1，这是函数最后执行的操作
    return binomCoeffTailHelper(n, k - 1, acc * (n - k + 1) / k);
}

代码说明 #

• 辅助函数binomCoeffTailHelper的最后一步是单一递归调用，符合尾递归要求，编译器可进行尾调用优化。
• 利用组合数对称性将k替换为较小值，能显著减少递归的次数，提升效率。
• 累加器acc逐步累积乘积结果，避免了原递归中两次调用后的加法操作，完全通过参数传递完成计算。

内容的提问来源于stack exchange，提问作者Jonas Jacob Biermann