[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)
