参考

1. 递归和栈帧的调用原理
2. 尾递归为啥能优化？
3. Python 与尾递归优化
4. 尾调用与尾递归
5. Python开启尾递归优化!
6. 尾调用优化——记一道面试题的思考
7. Trampoline
8. Trampoline (computing)

递归函数

假设我们需要计算阶乘 factorial「n! = 1 * 2 * 3 * ... * n」，用函数表示

image.png

fact(n) 用递归方式写：

def fact(n: int) -> int:
    if n == 1:
        return 1
    return n * fact(n - 1)

计算 fact(5)，过程如下：

> fact(5)
> 5 * fact(4)
> 5 * (4 * fact(3))
> 5 * (4 * (3 * fact(2)))
> 5 * (4 * (3 * (2 * fact(1))))
> 5 * (4 * (3 * (2 * 1)))
> 5 * (4 * (3 * 2))
> 5 * (4 * 6)
> 5 * 24
> 120

在每次递归调用的时候，都会产生一个临时变量，导致进程内存占用量变大。这样执行递归层数比较深的代码时，除了无谓的内存浪费，还可能导致著名的堆栈溢出错误。

在计算机中，函数调用是通过栈 Stack 这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，当数据返回值时，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出。

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison

理论上，所有的递归函数都可以写成循环的方式，避免对栈溢出，但循环的逻辑不如递归清晰。改成循环就是手动维护一些数据结构来缓存数据，而不是用系统的调用栈。

递归函数不断调用自身，这种机械的重复行为很适合机器来执行，但是由于调用栈大小的限制，我们需要对递归做优化 - 尾递归。

尾调用 Tail Call

尾递归 Tail Recursion 是一种特殊的尾调用 Tail Call

函数的最后一条执行语句是调用一个函数，这种形式就称为尾调用。

// 正确的尾调用，函数 / 方法的最后一行是调用 function2() 这个函数
public int function1() {
    return function2();
}

// 错误例子 1
// 调用完函数 / 方法后，又多了赋值操作
public int function1() {
    int x = function2();
    return x;
}

// 错误例子 2
// 调用完函数后，又多了运算操作
public int function2() {
    return function2() + 1;
}

// 错误例子 3
// f(x) 的最后一个动作其实是 reutrn null
public void function1() { function2(); }

尾递归 Tail Recursion

尾递归 Tail Recursion 是一种特殊的尾调用 Tail Call。
尾递归是递归的一种特殊情况。

In computer science, a tail call is a subroutine call performed as the final action of a procedure.^[1] If the target of a tail is the same subroutine, the subroutine is said to be tail-recursive, which is a special case of direct recursion.

尾递归是指，在函数返回的时候，调用自身本身，并且，return 语句不能包含表达式。

When dealing with recursive or mutually recursive functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating a new call stack frame each time.

普通的尾调用，栈一般没有问题。而尾递归，栈 Stack Frame 可能快速增长，因为尾递归调用也会创建新的栈帧。但是可以通过优化使得尾递归每次调用只占用一个栈帧，不会出现栈溢出的情况。

上面的 fact(n) 由于 return n * fact(n - 1) 引入乘法表达式，所以不是尾递归。要改成尾递归方式，主要是要把每一步的乘积传入到递归函数中：

def fact(n: int):
    return fact_iter(n, 1)

def fact_iter(num: int, product: int):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

fact(5) 对应的 fact_iter(5, 1) 调用如下：

> fact_iter(5, 1)
> fact_iter(4, 5)
> fact_iter(3, 20)
> fact_iter(2, 60)
> fact_iter(1, 120)
> 120

尾递归调用时，如果做了优化，栈不会增长，因此无论多少次调用也不会导致栈溢出。

特点

尾递归在普通尾调用的基础上，多出了 2 个特征：

1. 在尾部调用的是函数自身（Self-called）;
2. 可通过优化，使得计算仅占用常量栈空间。

尾递归函数要怎么写呢？一个比较实用的方法是先写出用循环实现的版本，再把循环中用到的局部变量都改为函数的参数，这样再进入下一层函数时就不需要再用到上一层函数的环境了，到最后一层时就包含了前面所有层的计算结果。

栈 & 栈帧

以 Java 为例。JVM 会为每个新创建的线程都创建一个栈 Stack。栈是用来存储栈帧 Stack Frame 的容器；而栈帧是用来保存线程状态的容器，其主要包括局部变量表 Local Variable Table，操作数栈 Operand Stack，动态连接 Dynamic Linking，和方法返回地址 Return Address 等信息。（Java 目前还不支持尾调用优化，但尾调用优化的原理是相通的。）

栈的意义在于 - 保持函数入口环境。

栈会对栈帧进行压栈和出栈操作：每当一个方法被执行时都会新创建一个栈帧（压栈，push），方法调用结束后即被销毁（出栈，pop）。

在方法 A 内部调用方法 B，就会在 A 的栈帧上叠加一个 B 的栈帧。在一个活动的线程中，只有在栈顶的栈帧才是有效的，称为当前栈帧 Current Stack Frame，这个栈帧所关联的方法被称为当前方法 Current Method。之后当方法 B 运行结束，将结果返回到 A 后，B 的栈帧才会出栈。

public int eat(){ return 5; } 

public int action(){ 
    int x = eat(); 
    return x; 
} 

public int imitate(){ 
    int x = action(); 
    return x; 
} 

public static void main(String[] args){ imitate(); }

image.png

尾调用优化 Tail Call Optimization

上面说到，函数栈的目的是保持入口环境。那么在什么情况下可以把这个入口环境优化掉？入口环境没有意义。

注意，只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则无法进行尾调用优化。例如:

def add_one(a):
    one = 1
    def inner(b):
        return b + one
    return inner(b)

对于编译到机器码执行的代码，不管是 AOT Ahead-Of-Time 预先编译，还是 JIT Just-In-Time 实时编译，只要将 call ... ret 指令改为 jump ...，就可以复用同一个栈帧。对于解释执行的代码，解释器本身有很多机会可以动态修改栈帧来做尾调用优化。

遗憾的是，大多数编程语言没有针对尾调用做优化，Python 解释器 - CPython 也没有，并默认限制了递归调用深度，所以即使把上面的 fact(n) 改成尾递归方式，也会导致栈溢出。

Python Shell 默认递归深度和修改递归深度代码如下：

import sys

sys.getrecursionlimit()

sys.setrecursionlimit(num)

而假如我们对上述示例代码改写成如下所示：

public int eat(){ return 5; } 

public int action(){ return eat(); } 

public int imitate(){ return action(); } 

public static void main(String[] args){ imitate(); }

如果尾调用优化生效，栈对应的状态就会为如下：

image.png

蹦床优化 Trampoline Optimizations

• As used in some Lisp implementations, a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline suffices to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Programmers can use trampolined functions to implement tail-recursive function calls in stack-oriented programming languages.^[1]

• Continuation-passing style is a popular intermediate format for compilers of function languages, because many control flow constructs can be elegantly expressed and tail call optimization is easy. When compiling to a language without optimized tail calls, one can avoid stack growth via a technique called trampolining. The idea is to not make the final continuation call inside the function, but to exit and to return the continuation to a trampoline. That trampoline is simply a loop that invokes the returned continuations. Hence, there are no nested function calls and the stack won’t grow.^[2]

实现尾调用优化的方式中，如果因为某些原因不能直接控制生成的机器代码，也不方便运行时修改栈帧，还有一种方案叫 Trampoline Optimizations 蹦床优化。

实现方式是，在函数调用时，先插入一个 trampoline 蹦床函数（Python 装饰器 / Java 注解）。使用这个蹦床函数调用尾递归函数，不让它进行递归，而是直接返回下次递归调用的函数，并由蹦床函数来进行下一次递归调用。这样一层层的递归调用就会变成蹦床函数一次次的迭代式函数调用。

这种 Trampoline 的尾递归优化，未必由编程语言本身（编译器 / 运行时）提供，一些灵活型比较强的语言本身就能实现这个过程。比如这里有一段使用 CPython 的实现代码。

#!/usr/bin/env python3
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys


class TailRecurseException(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
    if it is it's own grandparent, and catching such
    exceptions to fake the tail call optimization.

    This function fails if the decorated
    function recurses in a non-tail context.
    """
    def func(*args, **kwargs):
        f = sys._getframe()
        # sys._getframe(): 当前调用栈
        # f_back: 栈顶元素 next outer frame object
        # f_back.f_back: 栈顶第二元素
        # f_code: code object being executed in this frame
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func


@tail_call_optimized
def fib(i, current=0, next=1):
    if i == 0:
        return current
    else:
        return fib(i - 1, next, current + next)


@tail_call_optimized
def factorial(n, acc=1):  
    "calculate a factorial"
    if n == 0:
        return acc
    return factorial(n-1, n*acc)


print(factorial(10000))  
# prints a big, big number,
# but doesn't hit the recursion limit.

暴露了一个 tail_call_optimized 装饰器，就可以对符合条件的函数进行尾递归优化。

f.f_back.f_back.f_code 和 f.f_code 的值都是 func。

这段代码实现原理和 Trampoline 相同。作为 Python 代码，装饰器并不能修改被装饰的函数体，来让函数只返回下次递归需要的参数，不再进行递归调用。通过装饰器在每次递归调用函数前，抛出一个异常，将这次调用的参数写进异常对象，再在 Trampoline 里捕获这个异常，将参数读出来，然后进行迭代调用。