疊代

疊代（英語：iteration），一作迭代，是重複反饋過程的活動，其目的通常是為了接近並且到達所需的目標或結果。每一次對過程的重複被稱為一次「疊代」，而每一次疊代得到的結果會被用來作為下一次疊代的初始值。

在數學中

一個五邊形的疊代。將對角用直線段連起來得到一個五角星，後者中心圍成了一個倒過來的小五邊形。疊代地執行這一過程會產生一系列巢狀的五邊形和五角星。

數學中的疊代可以指函數疊代的過程，即反覆地運用同一函數計算，前一次疊代得到的結果被用於作為下一次疊代的輸入。即使是看上去很簡單的函數，在經過疊代之後也可能產生複雜的行為，衍生出具有難度的問題。這樣的例子可以參見考拉茲猜想和雜耍者序列（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）就是一個封裝了疊代的對象。