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

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

使用累加器：

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)

Answer 2

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

使用一种称为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具有整洁的特性，因此我们可以编写我们的函数来支持直接样式和延续传递样式。我们通过指定一个default函数作为延续来实现这一点–我们将在下面更详细地使用此技术，因此请确保您首先理解这里的内容

               # 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（3ⁿ）-因为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