使用Python递归创建Pascal的三角形

I'm working on a homework assignment that asks me to create a Pascal Triangle using a recursive function. Below is what I've managed so far along with what I was given to work with. I'm quite new to Python and programming so I've got no idea where to head from here, any help would be appreciated!

我正在做一个家庭作业,要求我使用递归函数创建一个Pascal三角形。以下是我到目前为止所处理的内容以及我的工作内容。我对Python和编程很陌生,所以我不知道从哪里开始,任何帮助都将不胜感激!

def combination(n, k):
    print((n - 1) / (k - 1)) + ((n - 1) / k)

def pascals_triangle(rows):
    for row in range(rows):
        answer = ""
        for column in range(row + 1):
            answer = answer + combination(row, column) + "\t"
        print(answer)

pascals_triangle(5)

1 个解决方案

#1

You are not, in fact, using recursion at all in your answer. I think you are trying to code the formula nCk = (n-1)C(k-1) + (n-1)Ck. You need, therefore, to call combination from within itself (with a guard for the "end" conditions: nC0 = nCn = 1):

事实上,你的答案中根本没有使用递归。我想你正在尝试编码公式nCk =(n-1)C(k-1)+(n-1)Ck。因此,您需要从内部调用组合(具有“结束”条件的保护:nC0 = nCn = 1):

def combination(n, k):
    if k == 0 or k == n:
        return 1
    return combination(n - 1, k - 1) + combination(n - 1, k)

def pascals_triangle(rows):
    for row in range( rows):
        answer = ""
        for column in range( row + 1):
            answer = answer + str(combination(row, column)) + "\t"
        print(answer)

pascals_triangle(5)

Output:

1   
1   1   
1   2   1   
1   3   3   1   
1   4   6   4   1

Note that this is a spectacularly inefficient way of doing this: you are calling combination many, many times with the same arguments each time you get a binomial coefficient. You might consider caching the coefficients you find as you go along.

请注意,这是一种非常低效的方法:每次获得二项式系数时,您使用相同的参数多次,多次调用组合。你可以考虑缓存你找到的系数。

The other problem with your code is that your combination function wasn't actually returning anything, it was simply printing a value and exiting (returning None).

您的代码的另一个问题是您的组合函数实际上没有返回任何内容,它只是打印一个值并退出(返回None)。

#1