再談循環&迭代&回溯&遞歸&遞推這些基本概念

循環：不斷重復進行某一運算、操作。

迭代：不斷對前一舊值運算得到新值直到達到精度。一般用于得到近似目標值，反復循環同一運算式（函數），并且總是把前一 次運算結果反代會運算式進行下一次運算

遞推：從初值出發反復進行某一運算得到所需結果。-----從已知到未知，從小到達（比如每年長高9cm，20年180，30后270）

回溯：遞歸時經歷的一個過程。

遞歸：從所需結果出發不斷回溯前一運算直到回到初值再遞推得到所需結果----從未知到已知，從大到小，再從小到大(你想進bat，那么編程就的牛逼，就得卸載玩者農藥，努力學習）。遞歸(Recursion)是從歸納法(Induction)衍生出來的。

一個運算（操作），可以通過不斷調用本身的運算形式，往往需要通過前一次的結果來得到當前運算的結果，因而，程序運行時，總是先一次次地「回溯」前一次的結果（回溯過程中這些結果是未知的，直到回溯到初值令回溯終止，再層層遞推回來得到當前要求的值）

一個完整的遞歸應該有下面三個條件，否則就是不合格的遞歸

1. 明確遞歸的終止方法（一個遞歸必須有他遞推到頭的界定，否則將會是無限遞歸 ）

2. 明確的終止時處理方法

3. 重復調用自身并縮小問題規模

死循環不會棧溢出而無限遞歸會出現棧溢出情況，詳情推薦閱讀：《遞歸-程序之美，及其與循環的區別》，但實際上業務模型幾乎不會遇到。

kidneyball知乎回答總結會精辟

在有循環的語言里，有的人認為尾遞歸優化除了炫技之外是完全無用的。其實不然，尾遞歸寫法在我看來有以下好處

1. 強迫你把循環寫成單獨的函數。這又有什么好處呢？這會影響你的編程風格，習慣使用尾遞歸之后，你的寫出一個幾百行大函數的機率會小得多。

2. 保證沒有副作用，統一使用不可變數據。在循環里，循環變量就是一個可變數據。作為人肉開發者，如果想保證自己的某段程序沒有副作用，最好的做法就是根本不要寫任何帶副作用的東西，這樣代碼審查時一眼看過去就能知道有沒有副作用。至于避免副作用有什么好處，這又可以寫一篇文章，這里就不展開了。

3. 轉換成惰性序列時比較好看。在某些語言里，尾遞歸形式基本上只要去掉循環變量（變成無限遞歸）, 把初始狀態作為首元素，就是一個能直接拿來用的惰性序列。

“遞歸”是一種思路，這種思路的特點是：我不關注問題本身，我只關注這個問題如何可以用一種可重復的方式分解為一些規模更小的子問題，以及這些子問題與原問題的關系。再加上當問題的規模足夠小的時候，存在一個簡單直接的解法。

遞推和遞歸還是迷糊，show code

//遞歸求解
function?fib(n){
????return?n?<2?1:fib(n-1)?+?fib(n-2);
}
//遞推求解
function?fib(n){
????let?start=0;
????let?fn=1;
????for?(let?i=0;i<n;i++)?{
????????let?t=fn;
????????fn=fn+start;
????????start=t;
????}
????return?fn;
}

不難看出，

程序的一般寫法就好比是數列的通項公式。
程序的遞歸寫法就好比是數列的遞推公式。

再談循環&迭代&回溯&遞歸&遞推這些基本概念 - 模型設計,領域設計,軟件設計, - 周陸軍的個人網站，不定時更新，文有不妥之處，請留言告知，多謝（再談系列多為總結性文章（搬磚湊））。

推薦文章：

程序員們，以后再也別問我遞歸的問題了

遞歸-程序之美，及其與循環的區別