<p>当一个过程可以在每个过程应用程序中重复多次时,为了实现一个尾部调用,我们必须以某种方式对多个递归调用进行排序</p>
<p>使用一种称为<a href="https://en.wikipedia.org/wiki/Continuation-passing_style" rel="nofollow noreferrer">continuation-passing style</a>的技术,我们可以在函数中添加第二个参数,告诉函数下一步的计算应该是什么</p>
<p>简单的CPS转换如下所示</p>
<pre><code>def my_func (x):
return x
def my_cps_func (x, k)
# k represents the "next step"
return k (x)
</code></pre>
<p>Python具有整洁的特性,因此我们可以编写我们的函数来支持直接样式<em>和延续传递样式。我们通过指定一个<em>default</em>函数作为延续来实现这一点–我们将在下面更详细地使用此技术,因此请确保您首先理解这里的内容</p>
<pre><code> # by default, pass x thru untouched
# this is known as the "identity" function
def add (x, y, k = lambda x: x):
return k (x + y)
# direct style
print (add (2, 3)) # 5
# continuation-passing style
add (2, 3, print) # 5
# direct and CPS mixed! invent your own freedom
print (add (2, 3, lambda sum: add (sum, sum))) # 10
</code></pre>
<p>你的<code>stair_climb</code>就像一个3-fibonacci过程(有时称为“<a href="https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Tribonacci_numbers" rel="nofollow noreferrer">tribonacci</a>”),只有你使用一个独特的<em>(1,2,4)</em>种子,而不是一个更传统的<em>(0,0,1)</em>种子-我们将展示<em>tribonacci</em>转换为CPS,然后我们再看看你的过程</p>
<pre><code>def tribonacci (n, k = lambda x: x):
if n == 0:
return k (0)
elif n == 1:
return k (0)
elif n == 2:
return k (1)
else:
return tribonacci (n - 1, lambda a:
tribonacci (n - 2, lambda b:
tribonacci (n - 3, lambda c:
k (a + b + c))))
for x in range (1,10):
print (tribonacci (x))
# 0
# 1
# 1
# 2
# 4
# 7
# 13
# 24
# 44
</code></pre>
<p>但是该函数的<a href="https://en.wikipedia.org/wiki/Time_complexity" rel="nofollow noreferrer">time complexity</a>是<em>O(3<sup>n</sup></em>)-因为lambdas可以抽象任意数量的值,所以可以通过使用多参数lambda进行大规模优化-这里我们计算<em>O(n)</em>中的相同答案,其中<code>lambda a, b, c: ...</code>表示我们的“种子”</p>
<pre><code> # by default, return the first value of the seed
def tribonacci (n, k = lambda a, b, c: a):
if n == 0:
# base seed values
return k (0, 0, 1)
else:
# the next seed (this is our "next step")
return tribonacci (n - 1, lambda a, b, c:
# new seed
# b is the "next a"
# c is the "next b"
# the sum of each is the "next c"
k (b, c, a + b + c))
for x in range (1,10):
print (tribonacci (x))
# 0
# 1
# 1
# 2
# 4
# 7
# 13
# 24
# 44
</code></pre>
<p>我们要做的就是把<code>k (0, 0, 1)</code>种子改成<code>k (1, 2, 4)</code></p>
<pre><code>def stair_climb (n, k = lambda a, b, c: a):
if n == 0:
return k (1, 2, 4)
else:
return stair_climb (n - 1, lambda a, b, c:
k (b, c, a + b + c))
for x in range (1,10):
print (stair_climb (x))
# 2
# 4
# 7
# 13
# 24
# 44
# 81
# 149
# 274
</code></pre>
<p>是的,如果你看每一行,每一个程序应用程序都在尾部</p>
<pre><code>def stair_climb (n, k = lambda a, b, c: a):
if n == 0:
# tail
return k (1, 2, 4)
else:
# tail
return stair_climb (n - 1, lambda a, b, c:
# tail
k (b, c, a + b + c))
</code></pre>
<p>但是你有一个更大的问题-Python没有尾部调用消除</p>
<pre><code>print (stair_climb (1000))
# RecursionError: maximum recursion depth exceeded in comparison
</code></pre>
<p>不用担心,一旦使用了延续传递样式,就会有<a href="https://stackoverflow.com/questions/43592016/how-do-i-replace-while-loops-with-a-functional-programming-alternative-without-t/43596323#43596323">all sorts of ways around that</a></p>