3

用于计算k从一组n项目中选择项目的方式数量的递归公式，表示C(n,k)为：

           1                    if K = 0
C(n,k) = { 0                    if n<k
           c(n-1,k-1)+c(n-1,k)  otherwise

我正在尝试编写一个使用此递归公式C进行计算的递归函数。C(n,k)我编写的代码应该根据我自己工作，但它没有给我正确的答案。

这是我的代码：

def combinations(n,k):
    # base case
    if k ==0:
        return 1
    elif n<k:
        return 0
    # recursive case
    else:
        return combinations(n-1,k-1)+ combinations(n-1,k)

答案应如下所示：

>>> c(2, 1)
0
>>> c(1, 2)
2
>>> c(2, 5)
10

但我得到其他数字......看不到我的代码中的问题所在。

4

3 回答 3

6

我会尝试颠倒这些论点，因为正如所写的那样n < k。

我想你的意思是：

>>> c(2, 1)
2
>>> c(5, 2)
10
于 2013-05-29T20:03:53.963 回答
5

例如，您的电话c(2, 5)意味着n=2和k=5（根据您在问题顶部对 c 的定义）。所以n < k结果应该是这样0。这正是您的实施所发生的事情。所有其他示例也确实产生了实际正确的结果。

您确定示例测试用例的参数顺序正确吗？因为它们都是c(k, n)-调用。所以要么这些调用是错误的，要么你定义中的顺序c是关闭的。

于 2013-05-29T20:13:01.567 回答
4

这是你真的不应该使用递归函数的时候之一。直接计算组合非常简单。对于某些事情，比如阶乘函数，使用递归没什么大不了的，因为无论如何它都可以使用尾递归进行优化。

原因如下：

为什么我们在编写程序时从不使用这个定义来定义斐波那契数列？

def fibbonacci(idx):
    if(idx < 2):
        return idx
    else:
        return fibbonacci(idx-1) + fibbonacci(idx-2)

原因是因为递归，它非常慢。出于同样的原因，应尽可能避免多次单独的递归调用。

如果您确实坚持使用递归，我建议您先阅读此页面。更好的递归实现每次只需要一个递归调用。 Rosetta 代码似乎也有一些非常好的递归实现。

于 2013-05-29T20:24:58.203 回答