[TOC]
# 什么是尾遞歸
簡單來講，尾遞歸是指在一個方法內(nèi)部，遞歸調(diào)用后直接r`eturn`，沒有任何多余的指令了。
比如，一個遞歸實現(xiàn)的累加函數(shù)
~~~java
public static int acc(int n){
if(n == 1){
return 1;
}
return n + acc(n - 1);
}
~~~
請問這個是尾遞歸么？答案是否定的。
可能有的人會說，明明最后一個步驟就是調(diào)用acc，為啥不是尾遞歸？
實際上，你看到的最后一個步驟不代表從指令層面來講的最后一步。這個方法的r`eturn`先拿到`acc(n-1)`的值，然后再將`n`與其相加，所以求`acc(n-1)`并不是最后一步，因為最后還有一個`add`操作。
把上面的代碼做個等價邏輯轉(zhuǎn)換就很清晰了。
~~~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);
}
~~~
遞歸調(diào)用后就直接返回了，這是真正的尾遞歸。
## 為啥尾遞歸容易優(yōu)化？
遞歸調(diào)用的缺點是方法嵌套比較多，每個內(nèi)部的遞歸都需要對應的生成一個**獨立的棧幀**，然后將棧幀都入棧后再調(diào)用返回，這樣相當于浪費了很多的棧空間。比如`acc(3)`，執(zhí)行過程如下圖：
如上圖可見，這個遞歸操作要同時三個棧幀存在于棧上才能收尾。
尾遞歸要避免的是，嵌套調(diào)用的展開導致的多個棧幀并存的情況。
## 那為啥尾遞歸就能避免這種情況呢？
`acc`這種遞歸相當于外層調(diào)用依賴內(nèi)層調(diào)用的結(jié)果，然后再做進一步的操作，最終由最外層的方法收口操作，返回最終結(jié)果。
但尾遞歸由于將外層方法的結(jié)果傳遞給了內(nèi)層方法，那外層方法實際上沒有任何利用價值了，直接從棧里踢出去就行了，所以可以保證同時只有一個棧幀在棧里存活，節(jié)省了大量?？臻g。
整個邏輯上來講是這樣的：
`main`方法將`accTail(3,0)`入棧
`accTail(3,0)`執(zhí)行`n--`，`sum+=3`，將兩個結(jié)果傳遞給下個`accTail`，即準備執(zhí)行`accTail(2,3)`。這時`accTail(3,0)`生命周期結(jié)束，出棧。
以此類推，`acc(2,3)`入棧出棧，`acc(1,5)`入棧出棧，最后得到最終結(jié)果6。
通過上面的邏輯分析，方法內(nèi)部只是執(zhí)行一系列操作，將操作結(jié)果傳遞給下一個遞歸調(diào)用，所以完全可以將調(diào)用遞歸方法之前的邏輯單獨抽出來一個沒有遞歸調(diào)用的方法，至于遞歸的邏輯改為由while循環(huán)控制調(diào)用流程，啥時候結(jié)束、啥時候進行下一次調(diào)用。因為剛才講了，尾遞歸下次操作之前能夠?qū)⑸洗螚尫?，可以保證只有一個相關的棧幀在棧里，因此改用循環(huán)控制足夠了。
# 示例
以計算斐波那契數(shù)列第n項為例，使用遞歸，尾遞歸，循環(huán)三種實現(xià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 );
}
```
循環(huán)：
~~~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;
}
}
~~~
# 尾調(diào)用
尾調(diào)用是函數(shù)式編程中一個很重要的概念，當一個函數(shù)執(zhí)行時的最后一個步驟是返回另一個函數(shù)的調(diào)用，這就叫做尾調(diào)用。
## 尾調(diào)用優(yōu)化
函數(shù)在調(diào)用的時候會在調(diào)用棧（call stack）中存有記錄，每一條記錄叫做一個調(diào)用幀（call frame），每調(diào)用一個函數(shù)，就向棧中push一條記錄，函數(shù)執(zhí)行結(jié)束后依次向外彈出，直到清空調(diào)用棧。
做如下優(yōu)化修改：
```js
function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();
```
尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用記錄，只要直接用內(nèi)層函數(shù)的調(diào)用記錄取代外層函數(shù)的調(diào)用記錄就可以了，**調(diào)用棧中始終只保持了一條調(diào)用幀**。
這就叫做尾調(diào)用優(yōu)化，如果所有的函數(shù)都是尾調(diào)用的話，那么在調(diào)用棧中的調(diào)用幀始終只有一條，這樣會節(jié)省很大一部分的內(nèi)存，這也是**尾調(diào)用優(yōu)化的意義**。
# 小結(jié)
* 當一個函數(shù)尾調(diào)用自身，就叫做尾遞歸。
* 尾調(diào)用優(yōu)化對遞歸操作意義重大，所以一些函數(shù)式編程語言將其寫入了語言規(guī)格。
* 尾遞歸的實現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。
通常遞歸都是在棧上根據(jù)調(diào)用順序依次申請空間進行運算，然后層層回調(diào)，這是基于上一層運算依賴于下一層的運算結(jié)果（或者說上一層的運算還沒用做完，需要下一層返回的結(jié)果）。
而尾遞歸的情況是下層計算結(jié)果對上層“無用”（上一層運算已經(jīng)做完，不依賴后續(xù)的遞歸），為了效率，直接將下一層需要的空間覆蓋在上一層上.。
# 參考
www.zhihu.com/question/20761771
[尾調(diào)用和尾遞歸](https://segmentfault.com/a/1190000014277519)
