Java 中的尾递归二项式系数函数

Question

我正在寻找实现一个尾递归函数来计算两个数字 n 和 k 的二项式系数。如果 k > n 则应返回 0。类似地，如果 n == k 或 k == 0 它应该返回 1。我像这样递归地实现了它，但显然这没有使用尾部调用的逻辑，但我似乎无法弄清楚如何连接两者计算到一个递归调用中。任何帮助，以及如何从正常的递归函数到尾递归实现的解释，我们将不胜感激。谢谢！

    public static long binomCoeffRecursive(int n, int k) {
        // TODO: Implement binomCoeff recursively.
        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);
    }

Answer 1

您无法使用该公式获得尾递归实现因为您无法像您希望的那样“将两个计算连接到一个递归调用中”。

有一些用于计算二进制系数的尾递归实现，但仅使用一次递归调用。 可以找到适合转换为尾递归的迭代实现，例如in Guava。 （披露：我写的。）