帕斯卡的三角形通过递归

我们可以pascal使用辅助函数定义一个递归，pairs

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)]
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]

---

说明

我们真正关心的是pascal功能–我们编写的其他所有内容都不符合我们的编写方式pascal，因此我将首先进行介绍。

编写递归函数的一种非常常见的方法是使用内部辅助函数来跟踪我们计算的各种状态。我们将使用此技术作为pascal功能的基础

def my_recursive_func (<parameters>):
  def aux (<state_parameters>):
    if (<base_condition>):
      return <base_value>
    else
      return aux(<updated_state>)
  return aux(<initial_state>)

我们已经知道如何为我们的pascal功能填写一些样板

• parameters应该只是n一个Integer，因为我们希望像pascal(3)或那样调用函数pascal(5)-不应接受其他任何参数
• state_parameters–我们现在只知道两件事：1）我们将需要一些m可n累加的值，1每次递增-和2）一些可让我们计算下一行的值；我们称它为prevPascal行，因为每行都是根据前一行计算得出的
• base_condition–当m == n我们知道已经生成了所需的所有行时，这就是我们要停止递归的时候
• base_value –这是返回的最后一个值–不确定应该是什么
• updated_state–我们将m使用进行m + 1更新，并且大概将使用某种数组连接来更新行–在编写更多代码之前不确定
• initial_state-我们将开始m在1和Pascal是第一行[1]

好，让我们填写到目前为止的内容

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return ?
    else:
      return aux(m + 1, ?)
  return aux(1, [1])

我们要做的是pascal建立这样的结果

[[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...]
# => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ]

因此，为了为其写入base_value和更新状态prev，我们需要考虑此返回类型。我们要返回[[Int]]，这是一个列表，因此base_value可以简单地是空列表[]。

这意味着在每个步骤中，我们实际上都希望将其也[prev]与（+）串联到递归结果中...

[prev] + aux(m + 1, <next_row>)

现在我们已经很接近了，让我们pascal再次更新以查看需要完成的工作

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, <next_row>)
  return aux(1, [1])

好的，这就是硬顶了–计算下一行，对吗？嗯，实际上还不错。

# given
[1,2,1]

# the next row is
[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]))     # [[1,2]]
print(pairs([1,2,3]))   # [[1,2],[2,3]]
print(pairs([1,2,3,4])) # [[1,2],[2,3],[3,4]]

好的，这使我们现在真的很接近。让我们pascal再次更新该函数以查看我们的位置

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, [1] + [x + y for (x,y) in pairs(prev)] + [1])
  return aux(1, [1])

圣烟！我们已经完成了。这aux与下一行的在线计算调用看起来有点忙寿。让我们添加另一个助手里面pascal叫compute到干净的东西了。现在我们完成了！

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])

---

彻底

如果要显示高飞的文本和提示，可以编写main如下所示的内容–这使所有I / O与我们的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()

# run program
main()

继续运行pascal(300)或取得一些令人印象深刻的结果