Я ответил на этот вопрос один раз до здесь . Перейдите по ссылке для объяснения того, как создавать рекурсивные функции, подобные этой.
def pairs (xs):
if 2 > len(xs):
return []
else:
return [xs[0:2]] + pairs(xs[1:])
def pascal (n):
def compute (prev):
return [1] + [x + y for (x,y) in pairs(prev)] + [1]
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, compute(prev))
return aux(1, [1])
for line in pascal(5):
print(line)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
Выше мы создаем новый [1] синглтон в трех местах; два из которых являются частью цикла compute. Мы должны создать его один раз и использовать повторно.
def pascal (n):
one = [1]
def compute (prev):
return one + [x + y for (x,y) in pairs(prev)] + one
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, compute(prev))
return aux(1, one)
Последнее усовершенствование, которое я мог бы предложить, - это использовать генератор вместо того, чтобы охотно возвращать все строки
def pascal (n):
one = [1]
def compute (prev):
return one + [x + y for (x,y) in pairs(prev)] + one
def aux (m, prev):
if (m > n):
return
else:
yield prev
yield from aux(m + 1, compute(prev))
yield from aux(1, one)
Теперь вы можете лениво вычислять вывод по мере его использования. Однако, если вы хотите все сразу, вы можете использовать list.
list(pascal(5))
# [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]