轉自：人機與認知實驗室

如涉版權請加編輯微信iwish89聯系

哲學園鳴謝

許多時候，人們對事物常常不能獲得絕對信号（态）的感知，那麼就嘗試選擇能否獲得變化信号（勢）的意識，這些變化既包括遞歸也涉及叠代。那麼兩者究竟有何區别呢？

先講個故事吧。

從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？“從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？‘從前有座山，山裡有座廟，廟裡有個老和尚，正在給小和尚講故事呢！故事是什麼呢？……’”。

這個故事永遠也講不完，因為沒有遞歸結束條件。老師講遞歸時總是說，遞歸很簡單，一個遞歸結束條件，一個自己調用自己。如果遞歸沒有結束條件，那麼就會無限遞歸下去。在編程的時候，沒有遞歸結束條件或者遞歸過深，一般會造成棧溢出。

遞歸算法一般用于解決三類問題：

(1)數據的定義是按遞歸定義的。（Fibonacci函數）

(2)問題解法按遞歸算法實現。（回溯）

(3)數據的結構形式是按遞歸定義的。（樹的遍曆，圖的搜索）

叠代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、适合做重複性操作的特點，讓計算機對一組指令（或一定步驟）進行重複執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。

為什麼使用叠代而不用遞歸呢？

很明顯，使用遞歸時每調用一次，就需要在棧上開辟一塊空間，而使用叠代就不需要了，因此，很多時候設計出了遞歸算法，還要想法設法修改成叠代算法。

假如現在我們不考慮編程，我們僅僅看一下上面使用遞歸和叠代求1 2 3… n的過程。

使用遞歸：

sum(5)

5 sum(4)

5 4 sum(3)

5 4 3 sum(2)

5 4 3 2 sum(1)

5 4 3 2 1 sum(0)

5 4 3 2 1 0

5 4 3 2 1

5 4 3 3

5 4 6

5 10

15

使用叠代

0 1=1

1 2=3

3 3=6

6 4=10

10 5=15

上面兩個計算過程所需的步驟都是O(n)。但是兩個計算過程的形狀不一樣。

遞歸過程是一個先逐步展開而後收縮的形狀，在展開階段，這一計算過程構造起一個推遲進行的操作所形成的的鍊條（這裡是 )，在收縮階段才會實際執行這些操作。這種類型的計算過程由一個推遲執行的運算鍊條刻畫，稱為一個遞歸計算過程。要執行這種計算過程，就需要維護以後将要執行的操作的軌迹。在計算1 2 3 … n時，推遲執行的加法鍊條的長度就是為了保存其軌迹需要保存的信息量，這個長度随着n值而線性增長，這樣的過程稱為線性遞歸過程。

叠代過程的形成沒有任何增長或收縮。對于任意一個n，在計算的每一步，我們需要保存的就隻有i,ret，這個過程就是一個叠代計算過程。一般來說，叠代計算過程就是那種其狀态可以用固定數目的狀态變量描述的結算過程。在計算1 2 … n時，所需的計算步驟與n成正比，這種過程稱為線性叠代過程。

程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略隻需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

叠代是重複反饋過程的活動，其目的通常是為了逼近所需目标或結果。每一次對過程的重複稱為一次“叠代”，而每一次叠代得到的結果會作為下一次叠代的初始值。

遞歸與叠代都是基于控制結構：叠代用重複結構，而遞歸用選擇結構。

舉個例子吧：你要給某個小孩子買玩具。

遞歸：你自己不太了解小孩子的需求，為了縮小範圍，讓你的兒子去給孫子挑選。兒子比你強點有限，但依然不太了解小孩子的需求。為了縮小範圍，你又讓你孫子去挑選。如此這般，直到找到合适的玩具。

叠代：你挑了一件覺得不行，又挑了一件又不行。如此這般，直到找到合适的玩具。

所以一句話：遞歸是自己調用自己，每次旨在縮小問題規模。叠代是自己執行很多次，每次旨在更接近目标。

叠代是逐漸逼近，用新值覆蓋舊值，直到滿足條件後結束，不保存中間值，空間利用率高。

遞歸是将一個問題分解為若幹相對小一點的問題，遇到遞歸出口再原路返回，因此必須保存相關的中間值，這些中間值壓入棧保存，問題規模較大時會占用大量内存。

相關鍊接

你讀過數學書，但你修煉過數林秘籍嗎？

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!