帕斯卡三角形中每一行的值 - 递归

Question

在下面的代码中：

def pascal_row(row):
    if row == 0:
        return [1]
    previous_row = pascal_row(row - 1)
    pairs = zip(previous_row[:-1], previous_row[1:])
    return [1] + map(sum, pairs) + [1]

如果我 print (pascal_row(5))，它 returns [1, 5, 10, 10, 5, 1] 这是正确的解决方案。

这是一个家庭作业，我们需要使用递归，不能使用任何循环或zip。

有人可以帮我相应地转换吗？谢谢！

Answer 1

您可以使用不同的递归函数 sliding_sum 来计算前一行的成对总和。然后，只需在两端附加 [1]。

def sliding_sum(someList):
    if len(someList) == 1:
        return []
    return [someList[0] + someList[1]] + sliding_sum(someList[1:])

def pascal_row(row):
    if row == 0:
        return [1]
    previous_row = pascal_row(row-1)
    new_row = [1] + sliding_sum(previous_row) + [1]
    return new_row

for i in range(6):
    print pascal_row(i)

输出

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

Answer 2

这是另一个涉及辅助函数的解决方案：

def pascal_row(row):
    if row == 0:
        return [1]
    return _pascal_row(row, 0, [1])

def _pascal_row(target_row, current_row, res):
    if target_row == current_row:
        return res
    else:
        res = [1] + [res[i] + res[i+1] for i in xrange(len(res) - 1)] + [1]
        return _pascal_row(target_row, current_row + 1, res)

print pascal_row(5) # [1, 5, 10, 10, 5, 1]

帕斯卡三角形中每一行的值 - 递归

Value for each row in Pascal Triangle - Recursion

python

recursion

pascals-triangle

输出