时间戳

首页 > 解决方案 > 用于查找组合而不达到python内置限制的递归函数

python - 用于查找组合而不达到python内置限制的递归函数

问题描述

我已经组合了一个函数，用于使用递归查找组合，而不会达到 python 中的内置限制。例如，您可以计算：choose(1000, 500)。这是它现在的样子：

def choose(n, k):
    if not k: 
    return 1 .
elif n < k: 
    return 0
else:
    return ((n + 1 - k) / k) * choose(n, k - 1)

它完全按照我想要的方式工作。如果 k 为 0，则返回 1，如果 n 小于 k，则返回 0（这是根据我在 wikipedia 上找到的数学定义）。但是，问题是我不太了解最后一行（我在浏览网页时发现的）。在我目前使用的最后一行之前，这是我在函数中的最后一行：

return choose(n-1,k-1) + choose(n-1, k)

我也在维基百科上找到了它（尽管我认为我也不是 100% 理解这个）。但是由于python中的内置限制，它总是会导致错误，而我正在使用的新行不会导致这样的错误。我知道新行在程序中的工作效率更高，因为例如我们不会将其拆分为两个子问题。

再说一遍..我要问的是，是否有任何善良的灵魂可以（以一种可以理解的方式）解释这行代码在函数中是如何工作的：

return ((n + 1 - k) / k) * choose(n, k - 1)

标签： pythonrecursioncombinations

解决方案

剧透：底线是你应该使用封闭的形式n! / (k! (n - k)!)。

在许多其他语言中，解决方案是使您的函数tail-recursive，尽管 Python 不支持这种优化。因此，实现递归解决方案根本不是最佳选择。

您可以使用 增加最大递归深度sys.setrecursionlimit，但这不是最优的。

一种改进是通过迭代计算n-choose-k。

def choose(n, k):
    if n < k:
        return 0

    ans = 1
    while k > 0:
        ans *= (n + 1 - k) / k
        k -= 1

    return ans

虽然，由于浮点运算，上述内容会累积错误。因此，最好的方法是使用n-choose-k的封闭形式。

from math import factorial

def choose(n, k):
    return factorial(n) / (factorial(k) * factorial(n - k))

推荐阅读