尾遞歸，遞歸優化

一、什麼是尾遞歸

程式調用自身的程式設計技巧稱為遞歸（ recursion）。尾遞歸是一種特殊的遞歸，遞歸形式的調用都出現在函數的末尾，我們稱這個

遞歸函數是尾遞歸的。

二、尾遞歸的優勢

尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代

碼。這個調用傳回時棧幀中并沒有其他事情可做，是以也就沒有儲存棧幀的必要了。通過覆寫目前的棧幀而不是在其之上重新添加

一個，這樣所使用的棧空間就大大縮減了，這使得實際的運作效率會變得高很多。

三、怎麼轉換尾遞歸

3.1 把中間結果值轉換為函數參數。

比如：

遞歸前，

long Rescuvie(long n) {      return (n == 1) ? 1 : n * Rescuvie(n - 1);  }

遞歸後，

long TailRescuvie(long n, long a) {      return (n == 1) ? a : TailRescuvie(n - 1, a * n);  }    long TailRescuvie(long n) {//封裝用的          return (n == 0) ? 1 : TailRescuvie(n, 1);  }

3.2 把遞歸結果用map或者數組存儲起來

動态規劃常用這種方法來優化

四、有些語言不支援尾遞歸怎麼辦？

進一步把尾遞歸轉換成循環提高效率。