Python中递归整数划分计算器出现未知问题

Question

我的递归程序计算整数分区的数目有点麻烦。

我写了以下内容：

def p(k, n):
    if k > n:
        return 0
    if k == 1:
        return 1
    else:
        return (p(k+1, n) + p(k, n-k))

def partitions(n):
    ans = 1
    for k in range(1, n/2):
        ans += p(k, n-k)
    return ans

这个算法是从维基百科的文章Partition (number theory)中实现的。下面是我的程序为前几个整数输出的内容：

^{pr2}$

我不确定为什么我的程序不能正常运行，因为我认为我正确地实现了递归和维基百科的算法。有人能帮我理解一下它在做什么吗？

Answer 1

我看到两个问题：

这个：

if k == 1:

应该是if k == n:，并且这个循环：

^{pr2}$

应该是range(1, n/2+1)或更好，range(1, n//2+1)以明确表示我们需要整数除法，因为Python中的range不包括上界。修好后，我得到：

>>> [partitions(i) for i in range(1,10)]
[1, 2, 3, 5, 7, 11, 15, 22, 30]

（您会注意到，它只有9个值。：^）

Answer 2

你有一个基本情况是错误的：

if k == 1:
    return 1

应该是

^{pr2}$

另外：

for k in range(1, n / 2):

应该是

for k in range(1, n / 2 + 1):

这是因为公式中的和是上界的包含，但在Python中，range不包括上界。然后：

print [partitions(i) for i in range(1, 8)]

给予

[1, 2, 3, 5, 7, 11, 15]

匹配Wikipedia article中给定的值。在