原文: Tricks of the trade: Recursion to Iteration, Part 4: The Trampoline

这是关于将递归算法转换为迭代算法系列文章中的第四篇。如果你没有阅读过前面的文章，你可能想在继续之前阅读。

在我们系列的第一篇文章中，我们展示了如果你能将一个算法的递归调用转换为尾部调用，你就可以消除这些尾部调用，使用简单方法创建一个算法的迭代版本。在这篇文章中，我们将看看另外一种消除尾部调用的方法：trampoline

trampoline背后的思想是：在进行尾部调用之前，手动将当前执行的帧从栈中移除，消除栈堆积

执行帧和栈

为了理解为什么我们可能要手动删除一个执行帧，让我们想想当我们调用一个函数时会发生什么。语言运行时需要一些地方来存储内部管理信息和函数可能使用的任何局部变量，因此它在堆栈上分配了一个新的执行帧。然后它把控制权交给函数。当函数完成后，它执行一个return语句。这条语句告诉运行时从栈中移除执行帧，并将控制权(以及任何结果)交还给调用者。

但如果函数没有马上返回呢？如果它发起了另外一个函数调用呢？在这种情况下，运行时必须为该调用创建一个新的执行帧，并将其推到栈上，放到当前帧之上。如果函数最后多次递归地调用自己，每次调用都会在栈上增加一个帧，很快我们就会吃掉很多栈空间。

消除栈堆积

为了避免这个问题，一些编程语言保证，每当一个函数进行尾部调用的时候，都会回收当前的执行帧。也就是说，如果函数调用了其他函数(或者自己递归)，只是逐字返回该函数的结果，那就是尾部调用。在这种情况下，运行时将回收当前函数的执行帧，然后再将控制权转移给另外一个函数，使得另外一个函数直接将其结果返回给原函数的调用者。这个过程称为尾部调用消除。

但是在像Python这样不提供尾部调用消除的语言中，每一次调用，即使是尾部调用，也会将一个新的帧推到栈上。因此，如果我们想防止栈堆积，就必须在进行尾部调用之前，自己以某种方式从栈中消除当前帧。

但是如何做呢？唯一显而易见的方法就是回到我们的调用者那里去消除当前的帧。如果我们想让它工作，那么，调用者必须愿意帮助我们。这就是trampoline的作用。它是我们消除栈堆积的合作者

Trampoline

以下是Trampoline的作用:

1. 它调用我们的函数f，让自己成为当前调用者
2. 当f要对自己进行递归尾部调用的时候，它返回指令call(f)(*args, **kwargs)。语言运行时会乖乖的将当前执行帧从栈中删除，并将控制权返回给Trampoline，并将指令传递给它。
3. Trampoline解释指令并回调f, 给它提供参数，再次让自己成为调用者。
4. 这个过程重复进行，直到f想要返回一个最终结果z；然后它返回新的执行result(z)代替，和之前一样，运行时将当前执行帧从堆栈中移除，并将控制权返回给Trampoline
5. 但现在当Trampoline解释新的指令的时候，它会把z返回给它的调用者，结束Trampoline

现在你可以看到蹦床(Trampoline)的名字是怎么来的了。当我们的函数使用返回语句从栈中移除自己的帧时，蹦床会用新的参数将控制权弹回给它

下面是一个简单的实现。首先，我们把对空窗的指令编码为元组，我们让call(f)(*args, **kwargs)成为(f, args, kwargs), 让result(z)成为(None, z, None):

1
2
3
4
5
6
7

def call(f):
  def g(*args, **kwargs):
    return f, args, kuwags
  return g

def result(value):
  return None, value ,None

现在让我们创建一个装饰器来包裹一个带有蹦床的函数，它将解释函数返回的指令。

1
2
3
4
5
6
7
8
9
10

import functools

def with_trampoline(f):
  @functools.wraps(f)
  def g(*args, **kwargs):
    h = f
    while h is not None:
      h, args, kwargs = h(*args,**kwargs)
    return args
  return g

注意，蹦床归结为三条线

1
2
3

while h is not None:
  h,args,kwargs = h(*args, **kwargs)
return args

基本上，蹦床一直调用函数h, 直到该函数返回一个result(z)指令，此时循环推出，z返回。原来的递归尾部调用已经被归结为一个while循环。递归已经变成了迭代。

例子: 阶乘

为了理解我们如何使用这个实现，让我们回到我们系列第一篇文章中阶乘的案例

1
2
3
4

def factorial(n):
  if n < 2:
    return 1
  return n*factorial(n-1)

第一步，和以前一样，先转换为尾部递归调用

1
2
3
4

def factorial(n, acc=1):
  if n < 2:
    return acc
  return factorial(n-1, acc*n)

现在我们可以创建一个使用蹦床的等价函数

1
2
3
4

def trampoline_factorial(n, acc=1):
  if n<2:
    return result(acc)
  return call(trampoline_factorial)(n-1, n*acc)

请注意，return语句是如何转换的

最后，我们可以用trampoline包裹这个函数，得到一个可调用的版本，我们可以像原来一样使用

1

factorial = with_trampoline(trampoline_factorial)

让我们来试一下

1
2

>>> factorial(5)
120

要想真正看清发生了什么，一定要使用Online Python Tutorial的可视化工具来逐步完成函数的原始，尾部递归和蹦床版本。只要打开这个链接就能看到了

为什么要使用蹦床

正如我在本文开头提到的那样，如果你能将函数的递归转换为尾部调用 – 这是使用蹦床的前提 – 你也可以使用简单方法将函数的递归转换为迭代，完全消除尾递归。比如，下面是简单方法对我们的原始阶乘函数的处理结果：

1
2
3
4

def factorial(n, acc=1):
  while n>1:
    n,acc = n-1, acc*n
  return acc

这个版本比蹦床更简单，更高效，所以为什么不一直使用简单方法呢？

答案是，简单方法很难应用于从循环内进行尾部调用的函数。回想一下，它在函数体周围引入了一个循环，并且使用continue语句替换掉尾部调用。但是，如果函数已经有了自己的循环，那么用continue语句替换其中一个循环中的尾部调用将会重新启动该内部循环，而不是整个循环。在这种情况下，你必须添加条件标志，以确保正确的循环重新启动。此时，可能使用蹦床会比较简单

也就是说，我几乎从来不使用蹦床。把一个函数搞成尾部调用的形式基本已经完成了十分之九。如果已经走到了这一步，我通常会走完剩下的路，得到一个紧凑的迭代版本。

那么，我们为什么要了解蹦床呢？有两个原因。第一，它在编程传说中有点常见，所以最好理解它。第二，它是通向一个更通用，更强大的技术的垫脚石：continuation-passing-style表达式，这是我们下次的主题(注!! 作者弃更了，并没有, 关于CPS可以查看这个笔记)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# result, 入参, 局部变量(a,c)，flag
stack = []
base_frame = [None, None, {}, 0]
first_frame = [None, (root, 'a'), {'a': None, 'c': None}, 0]
stack.append(base_frame)
stack.append(first_frame)
while len(stack) > 1:
    cur = stack[-1]
    result, arg, local, flag = cur
    arg, left_right = arg
    if flag == 0:
        if not arg:
            stack.pop()
            stack[-1][-2][left_right] = []
        else:
            stack[-1][-1] = 1
            new_frame = [None, (arg.left, 'a'), {}, 0]
            stack.append(new_frame)
    elif flag == 1:
        stack[-1][-1] = 2
        new_frame = [None, (arg.right, 'c'), {}, 0]
        stack.append(new_frame)
    elif flag == 2:
        b = [arg.val]
        ret = local['a'] + b + local['c']
        stack.pop()
        stack[-1][-2][left_right] = ret
return stack[0][-2]['a']