如何将此递归更改为尾递归? [英] how to change this recursion to tail recursion?
问题描述
这是我试图将其更改为尾递归的递归代码
here is the recursion code I am trying to change it to tail recursion
def stairClimb(n):
if n <= 3:
WaysToClimb = [1, 2, 4]
return WaysToClimb[n - 1]
else:
return stairClimb(n - 1) + stairClimb(n - 2) + stairClimb(n - 3)
推荐答案
当一个过程可以在每个过程应用程序中重复多次时，要实现尾调用，我们必须以某种方式顺序多次递归调用
When a procedure can recur multiple times per procedure application, to achieve a tail call, we must somehow sequence the multiple recursive calls
使用一种称为continuation-passing style的技术，我们可以添加第二个参数到我们的函数，它告诉我们的函数下一步我们的计算应该是什么
Using a technique called continuation-passing style, we can add a second parameter to our function that tells our function what the next step of our computation should be
一个简单的 CPS 转换看起来像这样
A simple CPS conversion looks like this
def my_func (x):
return x
def my_cps_func (x, k)
# k represents the "next step"
return k (x)
Python 具有简洁的特性，因此我们可以编写我们的函数来支持直接样式 和 连续传递样式.我们通过指定一个 default 函数作为延续来实现这一点——我们将在下面更多地使用这种技术，所以请确保你先在这里理解它
Python has neat features tho, so we can write our function to support both direct style and continuation-passing style. We do this by assigning a default function as the continuation – we'll use this technique more below, so make sure you understand it here first
# 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
您的 stair_climb 就像一个 3-fibonacci 程序(有时称为tribonacci") 只有您的使用独特的 (1,2,4) 种子，而不是更传统的 (0,0,1) 种子 - 我们将显示 tribonacci 转换为 CPS，然后我们将查看您的程序
Your stair_climb is like a 3-fibonacci procedure (sometimes called "tribonacci") only yours uses a unique (1,2,4) seed instead of a more traditional (0,0,1) seed – we'll show tribonacci converted to CPS then we'll look at your procedure after that
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
但是该函数的时间复杂度是O (3n) - 由于 lambdas 可以抽象任意数量的值，这可以通过使用多参数 lambda 进行大规模优化 - 这里我们在 O (n) 其中 lambda a, b, c: ... 代表我们的种子"
But the time complexity of that function is O (3n) - since lambdas can abstract any number of values, this can be massively optimized by using a multi-parameter lambda – here we compute the same answer in O (n) where lambda a, b, c: ... represents our "seed"
# 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
我们所要做的就是将 k (0, 0, 1) 种子更改为 k (1, 2, 4)
All we have to do is change the k (0, 0, 1) seed to k (1, 2, 4)
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
是的，如果你看每一行，每个程序应用程序都在尾部
And yep, if you look at each line, every procedure application is in tail position
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))
但是你有一个更大的问题——Python 没有尾调用消除
But you have a bigger problem – Python doesn't have tail call elimination
print (stair_climb (1000))
# RecursionError: maximum recursion depth exceeded in comparison
不用担心，一旦你使用了延续传递风格，就会有 各种方法
No worries, once you're using continuation-passing style, there's all sorts of ways around that
这篇关于如何将此递归更改为尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
