有多少种可能的组合？

Question

用于计算从一组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

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

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)-calls。因此，要么这些调用是错误的，要么是您对c的定义中的顺序不正确。

Answer 3

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

原因如下：

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

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

原因是，由于递归，它是慢得令人望而却步的。出于同样的原因，如果可能的话，应该避免多个单独的递归调用。

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