我们可以使用辅助函数
pairs定义一个递归的
pascal。
pascal将返回
[[Int]]（一个整数数组的数组）- 例如，
pascal(3)将返回：
[ [1],
[1, 1],
[1, 2, 1] ]
好的，我会先展示所有代码，然后逐步解释其中的某些部分。
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])
[print(line) for line in pascal(5)]
解释
我们真正关心的是 pascal 函数 - 我们编写所有其他函数的方式都源于我们编写 pascal 的方式，所以我将首先讲述这个。
编写递归函数的一种非常普遍的方法是使用一个内部辅助函数来跟踪计算的各种状态。我们将使用这种技术作为我们 pascal 函数的基础。
def my_recursive_func (<b><parameters></b>):
def aux (<b><state_parameters></b>):
if (<b><base_condition></b>):
return <b><base_value></b>
else
return aux(<b><updated_state></b>)
return aux(<b><initial_state></b>)
我们已经知道如何填写一些样板文件，以便于我们的pascal函数。
parameters应该只是一个整数n，因为我们期望像pascal(3)或pascal(5)这样调用函数，不接受其他参数。state_parameters - 我们现在只知道两件事：1）我们需要一些值m，它从1开始计数，每次递增1 - 2）一些值使我们能够计算下一行；我们将其称为prev，因为每个Pascal行都是基于前一行计算的。base_condition - 当m == n时，我们知道我们已经生成了所有所需的行，这是我们想要停止递归的时候。base_value - 这是最后返回的值 - 不确定应该是什么。updated_state - 我们将使用m + 1更新m，并且我们将更新行，可能使用某种数组连接方式 - 在编写更多代码之前不确定。initial_state - 我们将从1开始m，并且Pascal的第一行是[1]。
好的，让我们填写到目前为止的内容。
def pascal (<b>n</b>):
def aux (<b>m</b>, <b>prev</b>):
if (<b>m > n</b>):
return <b>?</b>
else:
return aux(<b>m + 1</b>, <b>?</b>)
return aux(<b>1</b>, <b>[1]</b>)
我们想要做的是让
pascal 建立我们的结果，类似于这样。
[[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...]
# => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ]
为了编写
prev的
base_value和更新状态，我们需要考虑此返回类型。我们想要返回
[[Int]]，这是一个列表，因此
base_value可以简单地是空列表
[]。
这意味着在每一步中，我们实际上希望将
[prev]与递归结果连接起来（使用
+）...
[prev] + aux(m + 1, <next_row>)
我们现在非常接近了，让我们再次更新 pascal，看看我们还需要完成什么。
def pascal (n):
def aux (m, prev):
if (m > n):
return <b>[]</b>
else:
return <b>[prev]</b> + aux(m + 1, <b><next_row></b>)
return aux(1, [1])
好的，现在来到了困难的部分——计算下一行，是吧？其实并不太难。
[1,2,1]
[1, (1 + 2), (2 + 1), 1]
另一个例子。
# given
[1, 4, 6, 4, 1]
# the next row is
[1, (1 + 4), (4 + 6), (6 + 4), (4 + 1), 1]
因此，模式如下：创建一个新数组，从1开始，然后对于前一行中的每对数字，将两个数字相加并将每个总和附加到数组中，最后附加另一个1。我们可以使用类似于以下列表推导式的Python表达式来表示它：
[1] + [x + y for (x,y) in pairs(prev)] + [1]
现在我们只需要想出那个“pairs”函数。 “pairs”应该遵循以下契约。
pairs([]) => []
pairs([a]) => []
pairs([a,b]) => [[a,b]]
pairs([a,b,c]) => [[a,b],[b,c]]
pairs([a,b,c,d]) => [[a,b],[b,c],[c,d]]
现在让我们实现它并验证我们的实现是否满足契约。请注意，我将此函数实现在
pascal之外，因为它是一个通用函数，可以单独使用。要计算帕斯卡三角形的行，我们需要添加数字对，但是获取这些数字对或数字的方式不应成为
pascal函数本身的责任。
def pairs (xs):
if 2 > len(xs):
return []
else:
return [xs[0:2]] + pairs(xs[1:])
print(pairs([]))
print(pairs([1]))
print(pairs([1,2]))
print(pairs([1,2,3]))
print(pairs([1,2,3,4]))
好的，现在我们已经非常接近了。让我们再次更新pascal函数，看看我们到哪里了。
def pascal (n):
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, <b>[1] + [x + y for (x,y) in pairs(prev)] + [1]</b>)
return aux(1, [1])
天啊！我们已经完成了。不过，内联计算下一行的调用看起来有点繁忙。让我们在pascal中添加另一个名为compute的辅助函数来简化事情。现在我们完成了！
def pascal (n):
<b>def compute (prev):
return [1] + [x + y for (x,y) in pairs(prev)] + [1]</b>
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, <b>compute(prev)</b>)
return aux(1, [1])
做到彻底
如果你想要显示那些滑稽的文本和提示，你可以像下面这样编写main函数——这将保持所有的输入/输出与我们的pascal和pairs函数分离。在程序早期考虑这种关注点的分离和副作用的管理非常重要，因为如果函数做了比我们想要的更多的事情，那么很难重复使用它们。
def main ():
try:
print("Pascal triangle generator")
n = int(input("Pascal(x): x = "))
if n < 1: raise
[print(line) for line in pascal(n)]
except:
print("enter a non-zero positive integer")
main()
main()
请放心运行pascal(300)或其他类似程序，你会得到令人印象深刻的结果。
triLvl()也是递归的？ - NiVeR