通过递归的帕斯卡三角形

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

我不知道这是否是您要找的，但它工作得很好：

from operator import add


def pascal(curlvl, newlvl, tri):
    if curlvl == newlvl:
        return ""
    elif curlvl == 0:
        tri.append(1)
        print (tri)
        return pascal(curlvl + 1, newlvl, tri)
    else:
        tmp = [1]
        rt = tri[:-1]
        rt.reverse()
        # print (map(add, rt, tri[:-1]))
        # In Python 3, map returns a generator.
        # Wrapping map in list makes this code compatible with
        # both Python 2 and 3
        tt = list(map(add, rt, tri[:-1]))
        if (len(tt) > 0):
            tmp.extend(tt)
        tmp.append(1)
        tri = tmp
        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 2

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

pascal 将 return [[Int]]（Int 数组的数组）——例如，pascal(3) 将 return

[ [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 (<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，直到 n – 和 2) 一些允许我们计算下一行的值；我们将其称为 prev，因为每个 pascal 行都是根据 previous 行
base_condition——当m == n我们知道我们已经生成了我们需要的所有行时，这就是我们想要停止递归的时候
base_value – 这是最后一个值 returned – 不太确定应该是什么
updated_state – 我们将使用 m + 1 更新 m 并且我们可能会使用某种数组连接来更新行 – 在我们编写更多代码之前不确定
initial_state – 我们将从 m 开始 1 并且帕斯卡的第一行是 [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 和更新状态，我们需要考虑此 return 类型。我们想要 return [[Int]]，这是一个列表，所以 base_value 可以简单地是空列表，[].

这意味着在每一步中，我们实际上想要获取 [prev] 并将其连接 (+) 到递归结果 ...

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

我们真的很接近了，让我们再次更新 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])

好的，难点来了——计算下一行，对吗？其实还不算太糟。

# 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 行，我们需要添加成对的数字，但是添加或如何我们不应该将这些成对或数字作为 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, <b>[1] + [x + y for (x,y) in pairs(prev)] + [1]</b>)
  return aux(1, [1])

我的天啊！我们已经完成了。 aux 调用下一行的内联计算看起来有点忙。让我们在 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 像下面这样的东西 – 这样可以将所有 I/O 与我们的 pascal 和 [=20= 分开] 职能。这种关注点分离和副作用管理很重要，需要在程序的早期考虑，因为很难重用功能超出我们预期的功能。

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) 或一些令人印象深刻的结果

Answer 3

作为列表的递归 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))

希望能帮到你，不知道'zip'和'map'算不算循环（肯定有循环）

通过递归的帕斯卡三角形

Pascal's Triangle via Recursion

python

recursion

pascals-triangle