python - 帕斯卡三角形通过递归

Question

有人能告诉我我当前的代码是否可能吗？我必须在不使用任何循环的情况下创建带有输入的 Pascal 三角形。我一定会递归。
我在这上面花了 3 天，这是我能想出的最好的输出。

def pascal(curlvl,newlvl,tri):

  if curlvl == newlvl:
    return ""

  else:

    tri.append(tri[curlvl])

    print(tri)
    return pascal(curlvl+1,newlvl,tri)


def triLvl():
  msg = "Please enter the number of levels to generate:"

  triheight = int(input(msg))

  if triheight < 1:
    print("\n Sorry, the number MUST be positive\n Please try again.")
    return triLvl()

  else:
    return triheight



def main():

   triangle = [1]

   curlvl = 0

   print("Welcome to the Pascal's triangle generator.")

   usrTri = triLvl()
   print(triangle)
   pascal(curlvl,usrTri,triangle)



main()

Answer 1

我们可以定义一个递归 pascal使用辅助函数，pairspascal将返回 [[Int]] (一个 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 ，一个整数，因为我们希望像 pascal(3) 一样调用我们的函数或 pascal(5)等 – 不应接受其他参数

state_parameters – 我们现在只知道两件事:1) 我们需要一些值 m计数到 n , 递增 1每次 - 和 2) 一些允许我们计算下一行的值；我们称之为 prev因为每个 pascal 行都是根据前一行计算的

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应该有以下契约(Contract)

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

现在让我们实现它并验证我们的实现是否符合契约(Contract)。注意，我在 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)或一些令人印象深刻的结果