[TOC]
# 什么是尾递归
简单来讲，尾递归是指在一个方法内部，递归调用后直接r`eturn`，没有任何多余的指令了。
比如，一个递归实现的累加函数
~~~java
public static int acc(int n){
if(n == 1){
return 1;
}
return n + acc(n - 1);
}
~~~
请问这个是尾递归么？答案是否定的。
可能有的人会说，明明最后一个步骤就是调用acc，为啥不是尾递归？
实际上，你看到的最后一个步骤不代表从指令层面来讲的最后一步。这个方法的r`eturn`先拿到`acc(n-1)`的值，然后再将`n`与其相加，所以求`acc(n-1)`并不是最后一步，因为最后还有一个`add`操作。
把上面的代码做个等价逻辑转换就很清晰了。
~~~java
public static int acc(int n){
if(n == 1){
return 1;
}
int r = acc(n - 1);
return n + r;
}
~~~
看，是不是还隐含一个add操作？
累加的尾递归写法是下面这样子的：
~~~java
public static int accTail(int n, int sum){
if(n == 1){
return sum + n;
}
return accTail(n - 1,sum + n);
}
~~~
递归调用后就直接返回了，这是真正的尾递归。
## 为啥尾递归容易优化？
递归调用的缺点是方法嵌套比较多，每个内部的递归都需要对应的生成一个**独立的栈帧**，然后将栈帧都入栈后再调用返回，这样相当于浪费了很多的栈空间。比如`acc(3)`，执行过程如下图：
如上图可见，这个递归操作要同时三个栈帧存在于栈上才能收尾。
尾递归要避免的是，嵌套调用的展开导致的多个栈帧并存的情况。
## 那为啥尾递归就能避免这种情况呢？
`acc`这种递归相当于外层调用依赖内层调用的结果，然后再做进一步的操作，最终由最外层的方法收口操作，返回最终结果。
但尾递归由于将外层方法的结果传递给了内层方法，那外层方法实际上没有任何利用价值了，直接从栈里踢出去就行了，所以可以保证同时只有一个栈帧在栈里存活，节省了大量栈空间。
整个逻辑上来讲是这样的：
`main`方法将`accTail(3,0)`入栈
`accTail(3,0)`执行`n--`，`sum+=3`，将两个结果传递给下个`accTail`，即准备执行`accTail(2,3)`。这时`accTail(3,0)`生命周期结束，出栈。
以此类推，`acc(2,3)`入栈出栈，`acc(1,5)`入栈出栈，最后得到最终结果6。
通过上面的逻辑分析，方法内部只是执行一系列操作，将操作结果传递给下一个递归调用，所以完全可以将调用递归方法之前的逻辑单独抽出来一个没有递归调用的方法，至于递归的逻辑改为由while循环控制调用流程，啥时候结束、啥时候进行下一次调用。因为刚才讲了，尾递归下次操作之前能够将上次栈帧释放，可以保证只有一个相关的栈帧在栈里，因此改用循环控制足够了。
# 示例
以计算斐波那契数列第n项为例，使用递归，尾递归，循环三种实现方式：
递归：
```js
int fibonacci(int n)
{
if (n == 0) return 0;
else if (n == 1) return 1;
else return fibonacci(n-1)+fibonacci(n-2);
}
```
尾递归：
```js
int fibonacci_tail(int n, int ret1, int ret2)
{
if (n == 0) return ret1;
else return fibonacci_tail( n-1, ret2, ret1 + ret2 );
}
```
循环：
~~~js
int fibonacci_cycle(int n)
{
int fib;
int f0 = 0;
int f1 = 1;
if (n == 0) return f0;
else if (n == 1) return f1;
else {
for (int $i = 2; $i <= n; $i++) {
fib = f0 + f1;
f0 = f1;
f1 = fib;
}
return fib;
}
}
~~~
# 尾调用
尾调用是函数式编程中一个很重要的概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用。
## 尾调用优化
函数在调用的时候会在调用栈（call stack）中存有记录，每一条记录叫做一个调用帧（call frame），每调用一个函数，就向栈中push一条记录，函数执行结束后依次向外弹出，直到清空调用栈。
做如下优化修改：
```js
function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();
```
尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，只要直接用内层函数的调用记录取代外层函数的调用记录就可以了，**调用栈中始终只保持了一条调用帧**。
这就叫做尾调用优化，如果所有的函数都是尾调用的话，那么在调用栈中的调用帧始终只有一条，这样会节省很大一部分的内存，这也是**尾调用优化的意义**。
# 小结
* 当一个函数尾调用自身，就叫做尾递归。
* 尾调用优化对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。
* 尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。
通常递归都是在栈上根据调用顺序依次申请空间进行运算，然后层层回调，这是基于上一层运算依赖于下一层的运算结果（或者说上一层的运算还没用做完，需要下一层返回的结果）。
而尾递归的情况是下层计算结果对上层“无用”（上一层运算已经做完，不依赖后续的递归），为了效率，直接将下一层需要的空间覆盖在上一层上.。
# 参考
www.zhihu.com/question/20761771
[尾调用和尾递归](https://segmentfault.com/a/1190000014277519)
