通过递归生成帕斯卡三角形

Question

我现在的代码真的能实现吗？我需要创建一个帕斯卡三角形，但是不能使用任何循环，只能用递归。

我已经花了三天时间在这个问题上，这是我能想到的最好结果。

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

递归生成的帕斯卡三角形列表：

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 2

我不知道这是不是你想要的，但它运行得很好：

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 3

我们可以用一个辅助函数 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)]
# [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，它会从 1 递增到 n；2) 需要一个值来计算下一行，我们称它为 prev，因为每一行的计算都是基于 上一行 的
• base_condition – 当 m == n 时，我们知道已经生成了所有需要的行，这时我们要停止递归
• base_value – 这是最后返回的值，目前还不太确定应该是什么
• updated_state – 我们会用 m + 1 来更新 m，并且可能会用某种数组拼接来更新行，具体要等写更多代码才能确定
• 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 的行，我们需要将数字成对相加，但如何获取这些数字对不应该由 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。这将所有的输入输出与我们的 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) 或其他的，看看一些令人印象深刻的结果。