迭代
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
迭代(英語:iteration),一作迭代,是重複反饋過程的活動,其目的通常是為了接近並且到達所需的目標或結果。每一次對過程的重複被稱為一次「迭代」,而每一次迭代得到的結果會被用來作為下一次迭代的初始值。
在數學中
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/40/Pentagon_iteration.svg/200px-Pentagon_iteration.svg.png)
數學中的迭代可以指函數迭代的過程,即反覆地運用同一函數計算,前一次迭代得到的結果被用於作為下一次迭代的輸入。即使是看上去很簡單的函數,在經過迭代之後也可能產生複雜的行為,衍生出具有難度的問題。這樣的例子可以參見考拉茲猜想和雜耍者序列(Juggler sequence)。又如一個簡單的二次變換x→x(1-x),它的迭代將形成一個具有混沌性質的動力系統。
迭代在數學中的另一應用是迭代法,用來對特定數學問題作數值解估計。牛頓法就是迭代法的一個例子。
在電腦中
[編輯]在計算機科學中,迭代是程序中對一組指令(或一定步驟)的重複。它既可以被用作通用的術語(與「重複」同義),也可以用來描述一種特定形式的具有可變狀態的重複。
在第一種意義下,遞歸是迭代的一個例子,但是通常使用一種遞歸式的表達。比如用0!=1,n!=n*(n-1)!來表示階乘。而迭代通常不是這樣寫的。
而在第二種(更嚴格的)意義下,迭代描述了在指令式編程語言中使用的編程風格。與之形成對比的是遞歸,它更偏向於聲明式的風格。
這裡是一個依賴於破壞性賦值的迭代的例子,以指令式的虛擬碼寫成:
var i, a = 0 // 迭代前初始化 for i from 1 to 3 // 重複3次 { a = a + i // a的值增加i } print a // 打印出數字6
在這個程序片段中,變量i的值會不斷改變,依次取值1、2和3。這種改變賦值——或者叫做可變狀態——是迭代的特徵。 這裡是二分法解方程的遞歸和迭代算法的比較。
遞歸:
確定開區間左邊界和右邊界,(L, R) 若L + 1 >= R(即不包含整數點),表示序列中不存在f(x) 取中位 M = (L + R) / 2 若f(M) == y,返回M 否則根據f(M)和y的關係遞歸查找(L, M)或(M, R)
迭代:
確定邊界(L, R) while (L + 1 < R) /* 區間中包含整點 */ 求中位M = (L + R) / 2 若f(M)等於y,退出循環 根據f(M)與y的關係執行 L = M 或 R = M,進入下一輪循環
在函數編程語言中,迭代可以用遞歸技巧來。
下述例子用Scheme語言寫成。注意它是一個遞歸(迭代的特例),因為函數iter在解決問題時調用了自身。特別地,它使用了尾部遞歸,一種能被Scheme這樣的編程語言完備支持的技巧,因此程序不會占用大量堆棧。
;; sum : number -> number
;; to sum the first n natural numbers
(define(sum n)
(if (and (integer? n) (> n 0))
(let iter ([n n] [i 1])
(if (= n 1)
i
(iter (- n 1) (+ n i))))
((assertion-violation
'sum "invalid argument" n))))
迭代器(iterator)就是一個封裝了迭代的對象。