如何将此递归更改为尾递归？

Question

这里是我试图将其更改为尾递归的递归代码

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)

Answer 1

当一个过程每个过程应用程序可以重复多次，为了实现尾调用，我们必须以某种方式对多个递归调用进行排序

使用一种名为continuation-passing style的技术，我们可以在我们的函数中添加第二个参数，告诉我们的函数我们计算的下一步应该是什么

简单的CPS转换看起来像这样

def my_func (x):
  return x

def my_cps_func (x, k)
  # k represents the "next step"
  return k (x)

Python有很多功能，所以我们可以编写我们的函数来支持直接样式和延续传递样式。我们通过指定默认函数作为延续来实现这一点 - 我们将在下面更多地使用此技术，因此请务必先在此处理解

               # 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然后我们将在此之后查看您的程序

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

但是该函数的time complexity是O（3n） - 因为lambdas可以抽象任意数量的值，这可以通过使用多参数lambda进行大规模优化 - 这里我们在O（n）中计算相同的答案，其中lambda a, b, c: ...代表我们的“种子”

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

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

是的，如果你看看每一行，每个程序应用程序都处于尾部位置

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没有尾部调用消除

print (stair_climb (1000))
# RecursionError: maximum recursion depth exceeded in comparison

不用担心，一旦你使用延续传递风格，就有all sorts of ways around that

Answer 2

使用累加器：

def stairClimb(n, acc, acc1, acc2):

if n == 3:
    return acc2
else:
    return stairClimb(n-1, acc1, acc2, acc+acc1+acc2)

并用初始数字调用它：

stairClimb(n, 1, 2, 4)