有多少种可能的组合

Question

计算从一组n项(记为C(n,k))中选择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

但我得到其他数字…请不要在我的代码中看到问题所在

Answer 1

我会尝试反转参数，因为正如n < k所写的。

我想你是这个意思:

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

Answer 2

您的呼叫，例如c(2, 5)意味着n=2和k=5(根据您在问题顶部对c的定义)。所以n < k，因此结果应该是0。这正是在你的实现中发生的事情。而且所有其他的例子也确实产生了正确的结果。

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

Answer 3

这是您确实不应该使用递归函数的情况之一。直接计算组合是非常简单的。对于某些东西，比如阶乘函数，使用递归没什么大不了的，因为它可以用尾递归进行优化。

原因如下:

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

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

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

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