Python递归实现帕斯卡三角形。

Question

完成了使用迭代函数创建Pascal三角形的任务后，我尝试使用递归函数重新创建。我已经达到了能够生成与传入参数对应的单个行的程度。但是多次尝试使其生成包括该行在内的整个三角形都失败了。我甚至尝试编写一个单独的函数，该函数迭代输入数字的范围，并在调用递归函数时将迭代的数字附加到单独的行列表中，然后返回该列表。期望的输出应该是一个列表，其中每个内部列表包含三角形的一行。格式如下：

[[1], [1, 1], [1, 2, 1]...]

相反，它返回一个杂乱无序的嵌套列表，完全由1填充。

这就是有问题的递归函数，在没有第二个函数附加行的情况下（我真的想要一个包含所有内容的函数）：

def triangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [1]
    else:
        new_row = [1]
        last_row = triangle(n-1)
        for i in range(len(last_row)-1):
            new_row.append(last_row[i] + last_row[i+1])
        new_row += [1]
    return new_row

要明确的是，我已经完成了指定任务，这只是为了更深入地理解递归...

迭代解决方案：

def triangle(n):
    result = []
    for row in range(n):
        newrow = [1]
        for col in range(1, row+1):
            newcell = newrow[col-1] * float(row+1-col)/col
            newrow.append(int(newcell))
        result.append(newrow)
    return result

- Verbal_Kint

---

看起来它只返回第n个列表。这是有意的吗？你当前的输出确切是什么？ - robert

为什么不传递一个列表的列表作为参数，而不是一个数字？特别是因为每一行的结果都取决于前一行的结果。 - Joel Cornett

你能否包含你的迭代解决方案以供参考？ - jpaugh

@robert 的意图是输出一个列表的列表，其中每个列表都是三角形的一行。我已经达到了这一点，但我尝试将行收集到一个列表中所做的任何尝试都导致任意嵌套的包含 1 的列表。 - Verbal_Kint

Answer 1

你只需要通过递归传递一个列表的列表，并取出该列表的最后一个元素（即三角形的最后一行）来构建新行即可。具体如下：

def triangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [[1]]
    else:
        new_row = [1]
        result = triangle(n-1)
        last_row = result[-1]
        for i in range(len(last_row)-1):
            new_row.append(last_row[i] + last_row[i+1])
        new_row += [1]
        result.append(new_row)
    return result

- happydave

---

没问题。递归可能会令人困惑。我建议使用大量的打印语句或一个好的调试器。 - happydave

这个还是会打印出 [1, 1] 吗？ - Timothy Leung

怎么样再为 n = 2 添加一个基本情况，返回 [1, 2, 1]。 - Timothy Leung

Answer 2

使用尾递归的另一种解决方案，替代happydave的解决方案：

def triangle(n, lol=None):
    if lol is None: lol = [[1]]
    if n == 1:
        return lol
    else:
        prev_row = lol[-1]
        new_row = [1] + [sum(i) for i in zip(prev_row, prev_row[1:])] + [1]
        return triangle(n - 1, lol + [new_row])

- Joel Cornett

---

我认为[x + y for x, y in zip([0] + prev_row, prev_row + [0])]更加清晰。 - Karl Knechtel

@KarlKnechtel：我觉得你是对的。不过我喜欢 zip(a,a[1:]) 这个技巧 :) - Joel Cornett

Answer 3

我认为这段代码会很有帮助，它可以绘制三角形并进行递归操作：

def traingle(n):
    if n == 1:
        print(1)
        return [1]
    else:
        answer = [1]
        print_able = '1 '
        previos = traingle(n-1)
        for index in range(len(previos)-1):
            eleman = previos[index]+previos[index+1]
            answer.append(eleman)
            print_able += str(eleman)+' '
        answer.append(1)
        print_able += '1'
        print(print_able)
        return answer


end = int(input())
traingle(end)

- Sir-Sorg

Answer 4

是的，正如Karl Knechtel所展示的那样，递归的Pascal三角形可以这样实现：

P=lambda h:(lambda x:x+[[x+y for x,y in zip(x[-1]+[0],[0]+x[-1])]])(P(h-1))if h>1 else[[1]]
print(P(10))

- Cépagrave