尾遞歸=遞歸+迭代？，尾遞歸

尾遞歸=遞歸+迭代？，尾遞歸

0 引言

       平時見慣了遞歸和迭代，遞歸直觀，但太占內存和時間，迭代運算快，但是不如遞歸代碼簡潔明了。那麼可不可以把這兩種算法的優點糅合在一起？答案是肯定的，尾遞歸就提供了這樣一種機制。

1 尾遞歸是什麼

       簡單地說，尾遞歸就是披著“遞歸”的外衣，卻擁有一顆“迭代”的心。外觀上看起來像遞歸，但內部進行了迭代的運算。下面舉例說明。

2 階乘示例

       2.1 先看階乘的迭代算法：

       2.2 再看階乘的遞歸算法：

       2.3 最後看階乘的尾遞歸算法：

3 斐波那契數列示例

       3.1 先看斐波那契數列的迭代算法：

       3.2 再看斐波那契數列的遞歸算法：

       3.3 最後看斐波那契數列的尾遞歸算法：

小結

       通過示例可以看出，尾遞歸都是帶著一個“迭代變量”不斷向深處遞歸，相當於邊遞歸，邊計算，等遞歸完成時，結果也計算出來了。值得一提的是尾遞歸只是借了遞歸的外殼，本質還是在迭代，所以在效率上，應該是與迭代相仿的。