<p>我们可以使用helper函数<code>pairs</code>来定义递归<code>pascal</code></p>
<p><code>pascal</code>将返回<code>[[Int]]</code>(Int数组的数组)–例如,<code>pascal(3)</code>将返回</p>
<pre><code>[ [1],
[1, 1],
[1, 2, 1] ]
</code></pre>
<p>好的,我会先给你看所有的代码,但是之后我会一步一步来解释某些代码</p>
^{pr2}$
<hr/>
<p><strong>说明</strong></p>
<p>我们真正关心的是<code>pascal</code>函数——我们写的其他所有东西都是按照我们写<code>pascal</code>的方式生成的,所以我将从这个开始。在</p>
<p>编写递归函数的一种非常常见的方法是使用内部辅助函数来跟踪计算的各种状态。我们将使用此技术作为<code>pascal</code>函数的基础</p>
<pre><code>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>)</code></pre>
<p>我们已经知道如何为我们的<code>pascal</code>函数填充一些样板文件</p>
<ul>
<li><code>parameters</code>应该是<code>n</code>,一个整数,因为我们希望像<code>pascal(3)</code>或{<cd13>}等调用我们的函数——不接受其他参数</li>
<li><code>state_parameters</code>-我们现在只知道两件事:1)我们需要一些值<code>m</code>,每次递增<code>n</code>,每次递增{<cd17>};2)一些允许我们计算下一行的值;我们将其称为<code>prev</code>,因为每个pascal行都是基于前一行的<em>计算的</li>
<li><code>base_condition</code>-当<code>m == n</code>我们知道我们已经生成了所需的所有行,这时我们就要停止递归了</li>
<li><code>base_value</code>-这是最后一个返回的值-还不太确定应该是什么</li>
<li><code>updated_state</code>-我们将使用<code>m + 1</code>更新<code>m</code>,我们将大概使用某种数组连接来更新行,直到我们编写更多代码时才确定</li>
<li><code>initial_state</code>–我们将从<code>1</code>开始<code>m</code>,pascal的第一行是<code>[1]</code></li>
</ul>
<p>好吧,让我们把目前为止的情况填写一下</p>
<pre><code>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>)</code></pre>
<p>我们想做的是让<code>pascal</code>建立我们的结果,就像这样</p>
<pre><code>[[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...]
# => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ]
</code></pre>
<p>因此,为了编写<code>base_value</code>和{<cd18>}的更新状态,我们需要考虑这个返回值<em>类型</em>。我们要返回<code>[[Int]]</code>,这是一个列表,因此{<cd21>}可以是空列表,<code>[]</code>。在</p>
<p>这意味着,在每一步中,我们实际上要将<code>[prev]</code>并连接(<code>+</code>)到递归结果中。。。在</p>
<pre><code>[prev] + aux(m + 1, <b><next_row></b>)</code></pre>
<p>我们已经很接近了,让我们再次更新<code>pascal</code>,看看我们需要完成什么</p>
<pre><code>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])</code></pre>
<p>好吧,那么接下来的问题就来了——计算下一行,对吧?其实也不算太糟。在</p>
<pre><code># given
[1,2,1]
# the next row is
[1, (1 + 2), (2 + 1), 1]
</code></pre>
<p>或者另一个例子</p>
<pre><code># given
[1, 4, 6, 4, 1]
# the next row is
[1, (1 + 4), (4 + 6), (6 + 4), (4 + 1), 1]
</code></pre>
<p>所以模式是这样的:创建一个以<code>1</code>开头的新数组,然后对于前一行中的每对数字,将这两个数字相加,并将每个和追加到数组中,最后再追加另一个<code>1</code>。我们可以用python来表达,就像使用这样的列表理解</p>
<pre><code>[1] + [x + y for (x,y) in pairs(prev)] + [1]
</code></pre>
<p>现在我们只需要找出<code>pairs</code>函数。<code>pairs</code>应具有以下合同</p>
<pre><code>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]]
</code></pre>
<p>现在让我们实现它,并验证我们的实现是否满足契约。注意,我在<code>pascal</code>的</em>之外实现这个函数,因为它是一个泛型函数,它本身就很有用。要计算pascal行,我们需要添加一对数字,但是添加或如何获得这些对或数字不应该留给<code>pascal</code>函数本身的责任。在</p>
<pre><code>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]]
</code></pre>
<p>好吧,这让我们很接近了。让我们再次更新<code>pascal</code>函数,看看我们现在所处的位置</p>
<pre><code>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])</code></pre>
<p>天哪!烟!我们已经做完了。使用下一行的内联计算的<code>aux</code>调用看起来有点忙。让我们在<code>pascal</code>中添加另一个名为<code>compute</code>的助手来清理。现在我们结束了!在</p>
<pre><code>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])</code></pre>
<hr/>
<p><strong>彻底</strong></p>
<p>如果你想显示愚蠢的文本和提示,你可以写一些<code>main</code>如下所示–这使所有的I/O与我们的<code>pascal</code>和<code>pairs</code>函数分开。这种关注点的分离和副作用的管理在程序的早期就要考虑到,因为很难重用功能,而这些功能比我们希望的要多。在</p>
<pre><code>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()
</code></pre>
<p>继续运行<code>pascal(300)</code>或其他什么来获得一些令人印象深刻的结果</p>