熱門:瘦小腿瘦小腿瘦小腿

  1. 首頁
  2. 科技日報
  3. 科技

什麼是遞迴?什麼是迭代?

  • 小白兔

  • 2019-03-31 09:41:50

許多時候,人們對事物常常不能獲得絕對訊號(態)地感知,那麼就嘗試選擇能否獲得變化訊號(勢)的意識,這些變化既包括遞迴也涉及迭代。那麼兩者究竟有何區別呢?

先講個故事吧。從前有座山,山裡有座廟,廟裡有個老和尚,正在給小和尚講故事呢!故事是什麼呢?“從前有座山,山裡有座廟,廟裡有個老和尚,正在給小和尚講故事呢!故事是什麼呢?‘從前有座山,山裡有座廟,廟裡有個老和尚,正在給小和尚講故事呢!故事是什麼呢?……’”。

這個故事永遠也講不完,因為沒有遞迴結束條件。老師講遞迴時總是說,遞迴很簡單,一個遞迴結束條件,一個自己呼叫自己。如果遞迴沒有結束條件,那麼就會無限遞迴下去。在程式設計的時候,沒有遞迴結束條件或者遞迴過深,一般會造成棧溢位。

遞迴演算法一般用於解決三類問題:

(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)。遞迴做為一種演算法在程式設計語言中廣泛應用。 一個過程或函式在其定義或說明中有直接或間接呼叫自身的一種方法,它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算,大大地減少了程式的程式碼量。遞迴的能力在於用有限的語句來定義物件的無限集合。一般來說,遞迴需要有邊界條件、遞迴前進段和遞迴返回段。當邊界條件不滿足時,遞迴前進;當邊界條件滿足時,遞迴返回。

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

遞迴與迭代都是基於控制結構:迭代用重複結構,而遞迴用選擇結構。

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

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

迭代:你挑了一件覺得不行,又挑了一件又不行。如此這般,直到找到合適的玩具。

所以一句話:遞迴是自己呼叫自己,每次旨在縮小問題規模。迭代是自己執行很多次,每次旨在更接近目標。

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

遞迴是將一個問題分解為若干相對小一點的問題,遇到遞迴出口再原路返回,因此必須儲存相關的中間值,這些中間值壓入棧儲存,問題規模較大時會佔用大量記憶體。

推薦您的文章

其他文章