为列表编写递归解决方案

Question

我试图写一个函数，它将返回第一个n个加泰罗尼亚数字的列表。到目前为止，这就是我想出来的。

def catalan_numbers(n):
    if n == 0:
        return 1
    else:
        n -= 1
        return int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan_numbers(n))

到目前为止，这为我提供了一个单一索引的正确解决方案。因此，如果我要打电话给catalan_numbers(4)，14就会被返回，这是正确的，但恰恰是我想要的。我试图解决这个问题，做了以下工作：

def catalan_numbers(n):
    catalan = [1]
    for x in range(0, n):
        catalan.append(int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan_numbers(n))
    return catalan

但这一结果是：

RuntimeError: maximum recursion depth exceeded in comparison

Answer 1

我建议迭代而不是递归：

def catalan_numbers(N):
    C = [1]
    for n in range(1, N):
        C.append((4*n - 2) * C[-1] // (n + 1))
    return C

Answer 2

错误的原因是，您没有大小写，还需要检查以下代码，而不是返回一个数字，而是返回一个列表，并将当前n个加泰罗尼亚数字与n-1的列表连接起来。

def catalan_numbers(n):
    if n == 0:
        return [1]
    else:
        n -= 1
        t = catalan_numbers(n)
        return t + [int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * t[-1])]