在數(shù)據(jù)結(jié)構(gòu)與算法中，重復(fù)執(zhí)行某個(gè)任務(wù)是很常見(jiàn)的，其與算法的復(fù)雜度密切相關(guān)。而要重復(fù)執(zhí)行某個(gè)任務(wù)，我們通常會(huì)選用兩種基本的程序結(jié)構(gòu)：迭代和遞歸。

迭代

「迭代 iteration」是一種重復(fù)執(zhí)行某個(gè)任務(wù)的控制結(jié)構(gòu)。在迭代中，程序會(huì)在滿足一定的條件下重復(fù)執(zhí)行某段代碼，直到這個(gè)條件不再滿足。

1.   for 循環(huán)

for 循環(huán)是最常見(jiàn)的迭代形式之一，適合預(yù)先知道迭代次數(shù)時(shí)使用。

以下函數(shù)基于 for 循環(huán)實(shí)現(xiàn)了求和  $1+2+?+n$  ，求和結(jié)果使用變量 res 記錄。需要注意的是，Python 中 range(a, b) 對(duì)應(yīng)的區(qū)間是“左閉右開(kāi)”的，對(duì)應(yīng)的遍歷范圍為  $a,a+1,\dots ,b?1$  。

iteration.cpp

/* for 循環(huán) */
int forLoop(int n) {
    int res = 0;
    // 循環(huán)求和 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        res += i;
    }
    return res;
}

圖 2-1 展示了該求和函數(shù)的流程框圖。

圖 2-1   求和函數(shù)的流程框圖

此求和函數(shù)的操作數(shù)量與輸入數(shù)據(jù)大小  $n$  成正比，或者說(shuō)成“線性關(guān)系”。實(shí)際上，時(shí)間復(fù)雜度描述的就是這個(gè)“線性關(guān)系”。相關(guān)內(nèi)容將會(huì)在下一節(jié)中詳細(xì)介紹。

2.   while 循環(huán)

與 for 循環(huán)類似，while 循環(huán)也是一種實(shí)現(xiàn)迭代的方法。在 while 循環(huán)中，程序每輪都會(huì)先檢查條件，如果條件為真則繼續(xù)執(zhí)行，否則就結(jié)束循環(huán)。

下面，我們用 while 循環(huán)來(lái)實(shí)現(xiàn)求和 1+2+?+n 。

iteration.cpp

/* while 循環(huán) */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // 初始化條件變量
    // 循環(huán)求和 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // 更新條件變量
    }
    return res;
}

在 while 循環(huán)中，由于初始化和更新條件變量的步驟是獨(dú)立在循環(huán)結(jié)構(gòu)之外的，因此它比 for 循環(huán)的自由度更高。

例如在以下代碼中，條件變量 i 每輪進(jìn)行了兩次更新，這種情況就不太方便用 for 循環(huán)實(shí)現(xiàn)。

iteration.cpp

/* while 循環(huán)（兩次更新） */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // 初始化條件變量
    // 循環(huán)求和 1, 4, ...
    while (i <= n) {
        res += i;
        // 更新條件變量
        i++;
        i *= 2;
    }
    return res;
}

總的來(lái)說(shuō)，for 循環(huán)的代碼更加緊湊，while 循環(huán)更加靈活，兩者都可以實(shí)現(xiàn)迭代結(jié)構(gòu)。選擇使用哪一個(gè)應(yīng)該根據(jù)特定問(wèn)題的需求來(lái)決定。

3.   嵌套循環(huán)

我們可以在一個(gè)循環(huán)結(jié)構(gòu)內(nèi)嵌套另一個(gè)循環(huán)結(jié)構(gòu)，以 for 循環(huán)為例：

iteration.cpp

/* 雙層 for 循環(huán) */
string nestedForLoop(int n) {
    ostringstream res;
    // 循環(huán) i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        // 循環(huán) j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; ++j) {
            res << "(" << i << ", " << j << "), ";
        }
    }
    return res.str();
}

圖 2-2 給出了該嵌套循環(huán)的流程框圖。

圖 2-2   嵌套循環(huán)的流程框圖

在這種情況下，函數(shù)的操作數(shù)量與 n^2 成正比，或者說(shuō)算法運(yùn)行時(shí)間和輸入數(shù)據(jù)大小 n 成“平方關(guān)系”。

我們可以繼續(xù)添加嵌套循環(huán)，每一次嵌套都是一次“升維”，將會(huì)使時(shí)間復(fù)雜度提高至“立方關(guān)系”、“四次方關(guān)系”、以此類推。

遞歸

「遞歸 recursion」是一種算法策略，通過(guò)函數(shù)調(diào)用自身來(lái)解決問(wèn)題。它主要包含兩個(gè)階段。

1. 遞：程序不斷深入地調(diào)用自身，通常傳入更小或更簡(jiǎn)化的參數(shù)，直到達(dá)到“終止條件”。
2. 歸：觸發(fā)“終止條件”后，程序從最深層的遞歸函數(shù)開(kāi)始逐層返回，匯聚每一層的結(jié)果。

而從實(shí)現(xiàn)的角度看，遞歸代碼主要包含三個(gè)要素。

1. 終止條件：用于決定什么時(shí)候由“遞”轉(zhuǎn)“歸”。
2. 遞歸調(diào)用：對(duì)應(yīng)“遞”，函數(shù)調(diào)用自身，通常輸入更小或更簡(jiǎn)化的參數(shù)。
3. 返回結(jié)果：對(duì)應(yīng)“歸”，將當(dāng)前遞歸層級(jí)的結(jié)果返回至上一層。

觀察以下代碼，我們只需調(diào)用函數(shù) recur(n) ，就可以完成  $1+2+?+n$  的計(jì)算：

recursion.cpp

/* 遞歸 */
int recur(int n) {
    // 終止條件
    if (n == 1)
        return 1;
    // 遞：遞歸調(diào)用
    int res = recur(n - 1);
    // 歸：返回結(jié)果
    return n + res;
}

圖 2-3 展示了該函數(shù)的遞歸過(guò)程。

圖 2-3   求和函數(shù)的遞歸過(guò)程

雖然從計(jì)算角度看，迭代與遞歸可以得到相同的結(jié)果，但它們代表了兩種完全不同的思考和解決問(wèn)題的范式。

• 迭代：“自下而上”地解決問(wèn)題。從最基礎(chǔ)的步驟開(kāi)始，然后不斷重復(fù)或累加這些步驟，直到任務(wù)完成。
• 遞歸：“自上而下”地解決問(wèn)題。將原問(wèn)題分解為更小的子問(wèn)題，這些子問(wèn)題和原問(wèn)題具有相同的形式。接下來(lái)將子問(wèn)題繼續(xù)分解為更小的子問(wèn)題，直到基本情況時(shí)停止（基本情況的解是已知的）。

以上述的求和函數(shù)為例，設(shè)問(wèn)題 f(n)=1+2+?+n 。

• 迭代：在循環(huán)中模擬求和過(guò)程，從 1 遍歷到 n ，每輪執(zhí)行求和操作，即可求得 f(n) 。
• 遞歸：將問(wèn)題分解為子問(wèn)題 f(n)=n+f(n?1) ，不斷（遞歸地）分解下去，直至基本情況 f(0)=0 時(shí)終止。

1.   調(diào)用棧

遞歸函數(shù)每次調(diào)用自身時(shí)，系統(tǒng)都會(huì)為新開(kāi)啟的函數(shù)分配內(nèi)存，以存儲(chǔ)局部變量、調(diào)用地址和其他信息等。這將導(dǎo)致兩方面的結(jié)果。

• 函數(shù)的上下文數(shù)據(jù)都存儲(chǔ)在稱為“棧幀空間”的內(nèi)存區(qū)域中，直至函數(shù)返回后才會(huì)被釋放。因此，遞歸通常比迭代更加耗費(fèi)內(nèi)存空間。
• 遞歸調(diào)用函數(shù)會(huì)產(chǎn)生額外的開(kāi)銷。因此遞歸通常比循環(huán)的時(shí)間效率更低。

如圖 2-4 所示，在觸發(fā)終止條件前，同時(shí)存在 n 個(gè)未返回的遞歸函數(shù)，遞歸深度為 n 。

圖 2-4   遞歸調(diào)用深度

在實(shí)際中，編程語(yǔ)言允許的遞歸深度通常是有限的，過(guò)深的遞歸可能導(dǎo)致棧溢出報(bào)錯(cuò)。

2.   尾遞歸

有趣的是，如果函數(shù)在返回前的最后一步才進(jìn)行遞歸調(diào)用，則該函數(shù)可以被編譯器或解釋器優(yōu)化，使其在空間效率上與迭代相當(dāng)。這種情況被稱為「尾遞歸 tail recursion」。

• 普通遞歸：當(dāng)函數(shù)返回到上一層級(jí)的函數(shù)后，需要繼續(xù)執(zhí)行代碼，因此系統(tǒng)需要保存上一層調(diào)用的上下文。
• 尾遞歸：遞歸調(diào)用是函數(shù)返回前的最后一個(gè)操作，這意味著函數(shù)返回到上一層級(jí)后，無(wú)需繼續(xù)執(zhí)行其他操作，因此系統(tǒng)無(wú)需保存上一層函數(shù)的上下文。

以計(jì)算 1+2+?+n 為例，我們可以將結(jié)果變量 res 設(shè)為函數(shù)參數(shù)，從而實(shí)現(xiàn)尾遞歸。

recursion.cpp

/* 尾遞歸 */
int tailRecur(int n, int res) {
    // 終止條件
    if (n == 0)
        return res;
    // 尾遞歸調(diào)用
    return tailRecur(n - 1, res + n);
}

尾遞歸的執(zhí)行過(guò)程如圖 2-5 所示。對(duì)比普通遞歸和尾遞歸，求和操作的執(zhí)行點(diǎn)是不同的。

• 普通遞歸：求和操作是在“歸”的過(guò)程中執(zhí)行的，每層返回后都要再執(zhí)行一次求和操作。
• 尾遞歸：求和操作是在“遞”的過(guò)程中執(zhí)行的，“歸”的過(guò)程只需層層返回。

圖 2-5   尾遞歸過(guò)程

Tip

請(qǐng)注意，許多編譯器或解釋器并不支持尾遞歸優(yōu)化。例如，Python 默認(rèn)不支持尾遞歸優(yōu)化，因此即使函數(shù)是尾遞歸形式，但仍然可能會(huì)遇到棧溢出問(wèn)題。

3.   遞歸樹(shù)

當(dāng)處理與“分治”相關(guān)的算法問(wèn)題時(shí)，遞歸往往比迭代的思路更加直觀、代碼更加易讀。以“斐波那契數(shù)列”為例。

Question

給定一個(gè)斐波那契數(shù)列 0,1,1,2,3,5,8,13,… ，求該數(shù)列的第 n 個(gè)數(shù)字。

設(shè)斐波那契數(shù)列的第 n 個(gè)數(shù)字為 f(0) ，易得兩個(gè)結(jié)論。

• 數(shù)列的前兩個(gè)數(shù)字為 f(1)=0 和 f(2)=1 。
• 數(shù)列中的每個(gè)數(shù)字是前兩個(gè)數(shù)字的和，即 f(n)=f(n?1)+f(n?2) 。

按照遞推關(guān)系進(jìn)行遞歸調(diào)用，將前兩個(gè)數(shù)字作為終止條件，便可寫(xiě)出遞歸代碼。調(diào)用 fib(n) 即可得到斐波那契數(shù)列的第 n 個(gè)數(shù)字。

recursion.cpp

/* 斐波那契數(shù)列：遞歸 */
int fib(int n) {
    // 終止條件 f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // 遞歸調(diào)用 f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // 返回結(jié)果 f(n)
    return res;
}

觀察以上代碼，我們?cè)诤瘮?shù)內(nèi)遞歸調(diào)用了兩個(gè)函數(shù)，這意味著從一個(gè)調(diào)用產(chǎn)生了兩個(gè)調(diào)用分支。如圖 2-6 所示，這樣不斷遞歸調(diào)用下去，最終將產(chǎn)生一個(gè)層數(shù)為 n 的「遞歸樹(shù) recursion tree」。

圖 2-6   斐波那契數(shù)列的遞歸樹(shù)

本質(zhì)上看，遞歸體現(xiàn)“將問(wèn)題分解為更小子問(wèn)題”的思維范式，這種分治策略是至關(guān)重要的。

• 從算法角度看，搜索、排序、回溯、分治、動(dòng)態(tài)規(guī)劃等許多重要算法策略都直接或間接地應(yīng)用這種思維方式。
• 從數(shù)據(jù)結(jié)構(gòu)角度看，遞歸天然適合處理鏈表、樹(shù)和圖的相關(guān)問(wèn)題，因?yàn)樗鼈兎浅＿m合用分治思想進(jìn)行分析。

兩者對(duì)比

總結(jié)以上內(nèi)容，如表 2-1 所示，迭代和遞歸在實(shí)現(xiàn)、性能和適用性上有所不同。

表 2-1   迭代與遞歸特點(diǎn)對(duì)比

Tip

如果感覺(jué)以下內(nèi)容理解困難，可以在讀完“?！闭鹿?jié)后再來(lái)復(fù)習(xí)。

那么，迭代和遞歸具有什么內(nèi)在聯(lián)系呢？以上述的遞歸函數(shù)為例，求和操作在遞歸的“歸”階段進(jìn)行。這意味著最初被調(diào)用的函數(shù)實(shí)際上是最后完成其求和操作的，這種工作機(jī)制與棧的“先入后出”原則是異曲同工的。

事實(shí)上，“調(diào)用?！焙汀皸臻g”這類遞歸術(shù)語(yǔ)已經(jīng)暗示了遞歸與棧之間的密切關(guān)系。

1. 遞：當(dāng)函數(shù)被調(diào)用時(shí)，系統(tǒng)會(huì)在“調(diào)用?！鄙蠟樵摵瘮?shù)分配新的棧幀，用于存儲(chǔ)函數(shù)的局部變量、參數(shù)、返回地址等數(shù)據(jù)。
2. 歸：當(dāng)函數(shù)完成執(zhí)行并返回時(shí)，對(duì)應(yīng)的棧幀會(huì)從“調(diào)用?！鄙媳灰瞥?，恢復(fù)之前函數(shù)的執(zhí)行環(huán)境。

因此，我們可以使用一個(gè)顯式的棧來(lái)模擬調(diào)用棧的行為，從而將遞歸轉(zhuǎn)化為迭代形式：

recursion.cpp

/* 使用迭代模擬遞歸 */
int forLoopRecur(int n) {
    // 使用一個(gè)顯式的棧來(lái)模擬系統(tǒng)調(diào)用棧
    stack<int> stack;
    int res = 0;
    // 遞：遞歸調(diào)用
    for (int i = n; i > 0; i--) {
        // 通過(guò)“入棧操作”模擬“遞”
        stack.push(i);
    }
    // 歸：返回結(jié)果
    while (!stack.empty()) {
        // 通過(guò)“出棧操作”模擬“歸”
        res += stack.top();
        stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}

觀察以上代碼，當(dāng)遞歸被轉(zhuǎn)換為迭代后，代碼變得更加復(fù)雜了。盡管迭代和遞歸在很多情況下可以互相轉(zhuǎn)換，但也不一定值得這樣做，有以下兩點(diǎn)原因。

• 轉(zhuǎn)化后的代碼可能更加難以理解，可讀性更差。
• 對(duì)于某些復(fù)雜問(wèn)題，模擬系統(tǒng)調(diào)用棧的行為可能非常困難。

總之，選擇迭代還是遞歸取決于特定問(wèn)題的性質(zhì)。在編程實(shí)踐中，權(quán)衡兩者的優(yōu)劣并根據(jù)情境選擇合適的方法是至關(guān)重要的。