最近學習了尾遞歸優化，發現與我之前認識的尾遞歸完全不一樣，特此記錄

什么是尾遞歸

1. 在我剛開始知道尾遞歸的時候，小看了尾遞歸，從字面意思去理解，這不就是在函數的末尾調用自身不就是尾遞歸了嗎。這有什么意義嗎？還特殊起一個名詞。
2. 后面我發現我還是太年輕了，不但錯誤理解了尾遞歸，還不知道尾遞歸是用來優化內存的。
3. 尾遞歸的真正定義：
   1. 在函數的最后一步！！！
      最后一步！！！
      最后一步！！！調用自身
   2. 并且在回歸過程中不能做任何操作！！！
      那就是在回歸過程中不能做任何操作！！！
      那就是在回歸過程中不能做任何操作！！！
   3. 符合上述兩個條件才可稱該遞歸為尾遞歸。
   4. 注意函的數最后一步和在函數末尾調用自身是不一樣的。尾遞歸的遞歸調用不是必須出現在函數的末尾。

首先需要分辨哪些遞歸才是尾遞歸的

1. 虛假的尾遞歸，以下遞歸看似是尾遞歸，實則不是尾遞歸。因為以下遞歸發返回的結果還要進行n*操作，所以不是尾遞歸的。

function x(n){
	return n === 1 ? 1 : n * x(n-1);
}

2. 真正的尾遞歸

function x(n, sum){
	return n === 1 ? sum : x(n-1, n * sum);
}

遞歸的優缺點

1. 遞歸的缺點

   • 遞歸相比循環有更大的內存消耗，從數據結構的角度上來講，就是一個普通循環的空間復雜度是1，而遞歸的空間復雜度是n。為什么遞歸的時間復雜度是n？因為遞歸n次，就要將函數入棧n次，每一次入棧都會有函數參數的聲明。所以是n。
   • 遞歸的執行效率實際上也是更慢的。盡管循環的時間復雜度是n，遞歸的時間復雜度也是n，但是無論是函數入棧、入棧，分配、釋放局部變量的內存、保存函數斷點、保存被調用函數的返回結果，這些操作實際上都需要時間。

2. 遞歸的優點

   • 有更好的可讀性和可維護性
   • 復雜問題用遞歸解決比循環更為優雅
   • 某些問題只能通過遞歸去解決。所有的循環的都可以用遞歸實現，但是不是所有的遞歸都可以轉換成循環去完成。（這里我也看過遞歸循環可以互相轉化的觀點，大家可以討論一下）

3. 可以看到遞歸缺點很多，但優點依然明顯，某些時候不得不用。

4. 用遞歸經常遇到的問題就是棧溢出，因為每次遞歸都要將函數入棧分配空間，遞歸次數特別多的時候是會爆棧的，盡管它有合理的退出條件。

為什么尾遞歸可以優化內存

1. 我們看尾遞歸的定義，在函數最后一步遞歸且在回歸過程中不能做任何操作。因為這個函數在回歸過程中不用進行任何操作，所以在函數調用棧里保存外層函數的執行信息是沒有必要的。當外層函數尾遞歸調用內層函數的時候，直接用內層函數頂替外層函數在函數調用棧里的位置就可以了。區別只是參數值變化了。不需要一層一層將遞歸函數入棧到遞歸調用棧里就優化了棧內存。
2. 有人會說我只是語言使用者，在語言層面無法操作函數調用棧啊？不用擔心，機智的語言設計者發現了這一點。基本所有的現代編程語言，在你使用尾遞歸時，都不會將遞歸函數重復循環的入棧，而是直接頂替外層函數。所以只要你的遞歸可以優化成尾遞歸調用方式并將其改成尾遞歸，那么你就完成了優化。
3. 所以遞歸函數的空間復雜度是n，如果你用了尾遞歸那么空間復雜度就變成了1。執行效率上也得到了提高。