编译器的尾部调用优化

尾调用是指某个方法或函数的最后一条指令是对另一个方法或函数的调用,尾部调用优化(Tail-Call Optimization)是编译器对尾部函数调用所做的一个处理,使得尾部函数调用不消耗额外的栈空间。一般的递归函数,每调用一层都要分配一定大小的栈空间来存放参数、临时变量和返回地址等数据,如果递归层数很深,会消耗大量的栈空间,甚至发生栈溢出。如果启用尾调用优化,递归中的每层调用都共享一个栈空间,能大提升栈内存的使用效率。

例如下面的 foo() 函数:

int foo(int a) {
    a = a + 1; 
    return bar(a);
}

函数 bar() 的调用是在函数 foo() 的最后一条语句,因此这是一个尾部调用。如果 foo() 函数在 bar() 返回之后执行了任何其它的指令,那么对 bar() 的调用就不再是一个尾部调用了。

如果一个函数f的最后一条指令又调用了另一个子函数 g(f 和 g 可以是同一个函数),那么执行到调用 g 的指令时,为 f 分配的栈中的数据已经失效,此时栈中的数据可以被改写,提供 g 必须的数据,再用一个简单的跳转指令跳转到 g,这样函数 g 在执行时可以复用 f 的栈,不需要为 g 分配额外的栈空间。

这对递归调用优为重要,可以使整个递归过程使用固定大小的栈空间,防止栈爆炸。

通常我们在实现斐波那契数列时会这样写:

int fact(int n) {
    if (n == 0)
        return 1;
    return n * fact(n-1);
}

上面的代码,fact() 调用返回后,还执行了 n 和 fact() 的返回值相乘的操作,所以对 fact() 的调用不是尾部调用,统译器不会进行尾部优化,每次对 fact() 的调用都会分配栈空间。改用下面的写法会更高效(递归过程中,fact_tc() 使用固定大小的栈空间):

int fact_tc(int i, int acc) { 
    if (i == 0) 
        return acc; 
    return fact_tc(i  1, acc * i);
}
int fact(int n) {
    return fact_tc(n, 1);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注