帕斯卡三角形与递归 [英] Pascals triangle with recursion

问题描述

好的，有人可以告诉我我当前的代码是否可行.我必须使用任何循环创建不带输入的帕斯卡三角形.我注定要递归.

Okay can someone tell me if my current code is even possible. I have to create pascals triangle with an input WITHOUT using any loops. I am bound to recursion.

我花了3天的时间，这是我能想到的最好的输出. 它让我发疯

Ive spent 3 days on this, and this is the best output that I can come up with. its driving me INSANE

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

We can define a recursive pascal using helper function, pairs

pascal将返回[[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，因为每帕斯卡行均基于上一个行
进行计算
• 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], ... ]

因此，要为prev编写base_value和更新状态，我们需要考虑此返回 type .我们要返回作为列表的[[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的 outside 函数，因为它是一个通用函数，它本身很有用.要计算帕斯卡行，我们需要添加数字对，但是不应将添加或如何获得这些对或数字作为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屋！