对于尾递归，很多人的理解仅局限于它是递归和尾调用的一个合体，比普通递归效率高。至于效率为什么高，高在哪，可能没有深究过。
1. 尾调用
要说尾递归，得先说尾调用。我理解的尾调用大概是这么一种情况：
- 函数A里面调用了函数B。
- 函数B执行后，函数A马上返回。
- 也就是说调用函数B（并返回执行结果）是函数A所做的最后一件事。
- 相当于执行完函数B后，函数A也就执行完。
因此在执行函数B时，函数A的栈帧其实是已经大部分没用了，可以被修改或覆盖。编译器可以利用这一点进行优化，函数B执行后直接返回到函数A的调用者。
// 尾调用
void test1() {
int a = 10;
int b = a +20;
test2(b);
}
//上面test1函数的最后一个动作是调用test2函数，所以可以认为test2(b);是尾调用
这里有一点需要注意：它是来自于编译器的优化。 这一点点的优化对于普通的尾调用来说可能意义不大，但是对于尾递归来说就很重要了。
2. 尾递归
尾递归是一种基于尾调用形式的递归，相当于前面说的函数B就是函数A本身。 即最后一个动作是调用自身，称为尾递归。
普通递归会存在的一些问题是，每递归一层就会消耗一定的栈空间，递归过深还可能导致栈溢出，同时又是函数调用，免不了push来pop去的，消耗时间。
采用尾调用的形式来实现递归，即尾递归，理论上可以解决普通递归的存在的问题。因为下一层递归所用的栈帧可以与上一层有重叠（利用jmp来实现），局部变量可重复利用，不需要额外消耗栈空间，也没有push和pop。
// 尾递归
void test2(int n) {
if (n < 0) return;
test2(n - 1);
}
再次提一下，它的实际效果是来自于编译器的优化（目前的理解）。在使用尾递归的情况下，编译器觉得合适就会将递归调用优化成循环。目前大多数编译器都是支持尾递归优化的。有一些语言甚至十分依赖于尾递归（尾调用），比如erlang或其他函数式语言（传说它们为了更好的处理continuation-passing style）。
假如不存在优化，大家真刀真枪进行函数调用，那尾递归是毫无优势可言的，甚至还有缺点——代码写起来不直观。
现代编译器的优化能力很强悍，很多情况下编译器优化起来毫不手软（于是有了volatile）。但有时编译器又很傲娇，你需要主动给它一点信号，它才肯优化。尾递归就相当于传递一个信号给编译器，尽情优化我吧！
3. 尾递归优化
一些编译器能对尾调用进行优化，以达到节省真空间的目的。
例如上面的示例代码，如果调用test1函数，则会为test1开辟栈空间，如果按照传统的思路，接下来调用test2时，则会为test2开辟一段新的栈空间，如下图所示
如果现在进行尾调用的优化的话，则是这样的：
首先调用test1，则会为test1开辟一段栈空间
接下来，如果要继续调用test2，编译器发现是尾调用，则会重复利用test1的这段栈空间，如下图所示:
将原来test1的栈空间，直接给test2使用。
不过，在这个过程当中，有很多技术细节。例如：现在调用test1函数时，系统为test1开辟了10个字节的栈空间，但是尾调用test2时，test2函数需要20个自己的栈空间，为了达到栈空间复用的目的，所以在调用test2函数时，就需要对test1函数的栈空间进行扩容。这样才能达到重复利用的目的。所以尾调用优化还是有一定难度的。
需要注意：尾调用这种优化，并不是所有的编译器都支持。例如有些编程语言是无法动态去修改栈帧的大小，就不能对尾调用进行优化。
4. 尾调用优化原理
尾调用优化也叫做尾调用消除（Tail Call Elimination）。
- 如果当前栈帧上的局部变量等内容都不需要用了，当前栈帧经过过适当的改变后可以直接当做被为调用的函数的栈帧使用，然后程序可以jump到被尾调用的函数代码
- 生成栈帧改变代码为jump的过程称作尾调用消除或尾调用优化
- 尾调用优化让位于尾位置的函数调用跟goto语句性能一样高
尾调用优化前的汇编代码（C++）
void test(int n) {
if (n < 0) return;
printf("test - %d\n",n);
test(n - 1);
}
可以发现，这一段代码是尾递归代码。在没有进行优化之前，生成的汇编代码如下：
从图中可以看到，在函数内部调用test函数时，使用的是call指令，又去调用test函数，在调用test函数时，有会开辟新的栈空间
如果开启了尾调用优化的话，最终生成的汇编代码如下：
以上就是关于尾调用和尾递归的优化。
参考文章：
网友评论