尾递归

尾调用(Tail Call)

尾调用：一个函数的最后一个动作是调用函数

• 如果最后一个动作是调用自身，则称为尾递归(Tail Recursion)，是尾调用的特殊情况

尾调用

void test1() {

int a = 10;

int b = a + 20;

test2(b); // 尾调用

}

尾递归

void test2() {

if (n < 0) return;

test2(n - 1); // 尾递归

}

• 一些编译器能对尾调用进行优化，以达到节省栈空间的目的

下列代码不是尾调用

int factorial(int n) {

if (n <= 1) return n;

return n * factorial(n - 1); // 不是尾调用，因为这里是做乘法

}

尾调用优化(Tail Call Optimization)

• 尾调用优化也叫做尾调用消除（Tail Call Elimination）
  • 如果当前栈帧上的局部变量等内容都不需要再使用了，当前栈帧经过适当的改变后可以直接当做被尾调用的函数的栈帧使用，然后程序可以跳转到被尾调用的函数代码处执行
  • 生成栈帧改变代码与跳转的过程，称为尾调用消除或尾调用优化
  • 尾调用优化可以让位于尾位置的函数调用具有跟goto语句一样高的性能
• 消除尾递归里的尾调用比消除一般的尾调用容易得多，因为栈帧大小保持不变，无需调整栈帧
  • JVM会消除尾递归里的尾调用，但不会消除一般的尾调用，因为JVM无法动态改变栈帧大小
  • 尾递归优化相对普遍，平时的递归代码可以尽量考虑使用尾递归的形式