带递归的帕斯卡三角形

Question

好吧，有人能告诉我我现在的代码是否可行。我必须在不使用任何循环的情况下使用输入创建pascals三角形。我注定要递归。在

我花了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三角形列表：

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”是否被视为循环（它们肯定包含循环）。在

Answer 3

我们可以使用helper函数pairs来定义递归pascal

pascal将返回[[Int]]（Int数组的数组）–例如，pascal(3)将返回

[ [1],
  [1, 1],
  [1, 2, 1] ]

好的，我会先给你看所有的代码，但是之后我会一步一步来解释某些代码

^{pr2}$

---

说明

我们真正关心的是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)或{}等调用我们的函数——不接受其他参数
• state_parameters-我们现在只知道两件事：1）我们需要一些值m，每次递增n，每次递增{}；2）一些允许我们计算下一行的值；我们将其称为prev，因为每个pascal行都是基于前一行的计算的
• base_condition-当m == n我们知道我们已经生成了所需的所有行，这时我们就要停止递归了
• base_value-这是最后一个返回的值-还不太确定应该是什么
• updated_state-我们将使用m + 1更新m，我们将大概使用某种数组连接来更新行，直到我们编写更多代码时才确定
• initial_state–我们将从1开始m，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和{}的更新状态，我们需要考虑这个返回值类型。我们要返回[[Int]]，这是一个列表，因此{}可以是空列表，[]。在

这意味着，在每一步中，我们实际上要将[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行，我们需要添加一对数字，但是添加或如何获得这些对或数字不应该留给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)或其他什么来获得一些令人印象深刻的结果