帕斯卡三角形通过递归 [英] Pascal's Triangle via Recursion

问题描述

有人能告诉我我当前的代码是否可行吗?我必须在不使用任何循环的情况下创建带有输入的 Pascal 三角形.我一定会递归.

Can someone tell me if my current code is even possible? I have to create Pascal's Triangle with an input without using any loops. I am bound to recursion.

我为此花了 3 天时间，这是我能想出的最佳输出.

I have spent 3 days on this, and this is the best output that I can come up with.

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

推荐答案

我们可以使用辅助函数pairs

pascal 将返回 [[Int]](一个 Int 数组的数组)——例如，pascal(3) 将返回

pascal will return [[Int]] (an Array of Arrays of Int) – eg, pascal(3) would return

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

好的，所以我会先向您展示所有代码，然后我会逐步解释某些部分

OK, so I'll show you all the code up front, but then I'll step thru and explain certain bits afterward

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 的方式中诞生的，所以我将从结束了.

What we really care about is the pascal function – everything else we've written was born out of the way we write pascal, so I'll start by going over that.

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

A very common way to write recursive functions is to use an inner auxiliary function that keeps track of our computation's various states. We'll be using this technique as the basis of our pascal function

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 函数填充一些样板

We already know how to fill in some of this boilerplate for our pascal function

• parameters 应该只是 n，一个整数，因为我们希望像 pascal(3) 或 pascal 一样调用我们的函数(5) 等 - 不应接受其他参数
• state_parameters – 我们现在只知道两件事:1) 我们需要一些值 m 计数到 n，递增1 每次 - 和 2) 一些允许我们计算下一行的值；我们将其称为 prev，因为每个 pascal 行都是基于 上一行 计算的
• base_condition – 当 m == n 我们知道我们已经生成了我们需要的所有行时，这是我们想要停止递归的时候
• base_value - 这是最后一个返回的值 - 不太确定应该是什么
• updated_state – 我们将使用 m + 1 更新 m 并且我们将大概使用某种数组连接更新行 – 不完全是确定直到我们编写更多代码
• initial_state – 我们将从 1 开始 m 并且 pascal 的第一行是 [1]

• parameters should just be n, an Integer, because we expect to call our function like pascal(3) or pascal(5), etc – no other arguments should be accepted
• state_parameters – we only know two things right now: 1) we will need some value m that counts up to n, incrementing by 1 each time – and 2) some value that allows us to compute the next row; we'll call it prev since each pascal row is computed based on the previous row
• base_condition – when m == n we know we've generated all the rows we need, this is when we want to stop recursing
• base_value – this is the last value returned – not quite sure what that should be yet
• updated_state – we will update m using m + 1 and we will update the rows presumably using some kind of array concatenation – not exactly sure until we write more code
• initial_state – we will start m at 1 and the first row of pascal is [1]

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

OK, let's fill in what we have so far

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

我们想要做的是让 pascal 像这样构建我们的结果

What we'd like to do is is have pascal build our result something like this

[[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可以简单地是空列表，[].

So in order to write the base_value and updated state for prev, we need to consider this return type. We want to return [[Int]], which is a list, so the base_value can simply be the empty list, [].

这意味着在每一步中，我们实际上都希望将 [prev] 和 (+) 连接到递归结果中......

That means in each step, we actually want to take [prev] and concatenate (+) it to the recursive result as well ...

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

我们现在已经很接近了，让我们再次更新 pascal 看看我们必须完成什么

We're getting really close now, let's update pascal again to see what we have to finish up

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

好的，那么难点来了——计算下一行，对吧?嗯，其实还不错.

Ok, so here comes the hard pard – calculating the next row, right? Well it's not too bad actually.

# 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 中表达，就像使用这样的列表理解

So the pattern is something like this: Create a new array starting with 1, then for each pair of numbers in the previous row, add the two numbers together and append each sum to the array, then finally append another 1. We might express that in python like using a list comprehension like this

[1] + [x + y for (x,y) in pairs(prev)] + [1]

现在我们只需要弄清楚 pairs 函数.pairs 应该有如下合约

Now we just need to figure out that pairs function. pairs should have the following 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]]

让我们现在实现它并验证我们的实现是否符合合同.请注意，我在 pascal 的之外 实现了这个函数，因为它是一个通用函数并且本身就很有用.要计算 pascal 行，我们需要添加数字对，但添加或如何获得这些对或数字不应由 pascal 函数本身负责.

Let's implement it now and verify that our implementation fulfills the contract. Note, I'm implementing this function outside of pascal because it's a generic function and useful on its own. To compute pascal rows, we need to add pairs of numbers, but adding or how we get those pairs or numbers should not be left as a responsibility for the pascal function itself.

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 函数，看看我们在哪里

OK, that's getting us really close now. Let's update the pascal function again to see where we're at

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 的助手来清理它.现在我们完成了！

Holy smokes! We're already done. That aux call with the inline computation of the next row looks a little busy tho. Let's add another helper inside pascal called compute to clean things up. Now we're done!

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 函数.在程序的早期考虑这种关注点分离和副作用管理很重要，因为重用功能超出我们希望的功能是很困难的.

If you want that goofy text and prompts to display, you can write main something like below – This keeps all the I/O separate from our pascal and pairs functions. This separation of concerns and managing of side-effects is important to consider early in your program because it's difficult to re-use functions that do more than we want them to.

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) 或其他东西以获得一些令人印象深刻的结果

Go ahead and run pascal(300) or something for some impressive results

这篇关于帕斯卡三角形通过递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！