python - Calculating Catalan Numbers

Question

I am trying to use this code to calculate the Catalan Number in Python, but it just does not work. How can I fix it?

Here is the code I have:

def catalan_rec(n):
    if n == 0:
        return 1
    else:
        b = 0
        for i in range (n):
            b += sum((catalan_rec(i))*(catalan_rec(n-1-i)))
    return b

Answer 1

问题是你在求和，你实际上应该乘法。来自维基百科的定义是：

您可以更好地使用 for 循环而不是递归：

def catnumber(n):
  ans = 1.0
  for k in range(2,n+1):
     ans = ans *(n+k)/k
  return ans

编辑 2

我认为公式不正确，但问题实际上是它使用整数除法，因此对子结果进行了四舍五入。解决方案是使用浮点变量，我通过初始化来做到这一点ans=1.0。

Answer 2

换行：

b += sum((catalan_rec(i))*(catalan_rec(n-1-i)))

为了：

b += (catalan_rec(i))*(catalan_rec(n-1-i))

您将一个整数作为参数传递给函数sum()，该函数只接受一个可迭代的。

Answer 3

这似乎对我有用（来自你的代码）

def catalan_rec(n):
    b = 0
    if n == 0:
        return 1
    else:
        for i in range (n):
            b += (catalan_rec(i))*(catalan_rec(n-1-i))
    return b

print catalan_rec(5)

出去：

42