Hello 算法迭代與遞迴深度解析——從 for/while 迴圈到呼叫堆疊、尾遞迴與遞迴樹【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技術指南聚焦《Hello 算法》中「迭代與遞迴」這一核心主題系統講解兩種基本的程式控制結構如何支撐起時間複雜度與空間複雜度分析的學習。文章將以 迭代與遞迴 原文為骨架結合倉庫內 Python、Java、C 等多語言原始碼深入剖析 for 迴圈、while 迴圈、巢狀迴圈、遞迴呼叫堆疊、尾遞迴最佳化與遞迴樹的底層原理。讀完本文你將掌握迭代與遞迴的實現技巧、兩者在時間/空間效率上的差異以及如何用顯式堆疊將遞迴改寫為迭代。在演算法中重複執行某個任務是非常常見的它與複雜度分析息息相關。因此在正式介紹時間複雜度和空間複雜度之前必須先理解兩種基本的程式控制結構迭代iteration與遞迴recursion。迭代重複執行任務的控制結構迭代是一種重複執行某個任務的控制結構。在迭代中程式會在滿足一定條件下重複執行某段程式碼直到這個條件不再滿足。迭代通常依賴迴圈語句實現最常見的形式包括for迴圈與while迴圈。for 迴圈適合預先知道迭代次數for迴圈是最常見的迭代形式之一適合在預先知道迭代次數時使用。以下函式基於for迴圈實現了求和 $1 2 \dots n$求和結果使用變數res記錄。注意 Python 中range(a, b)對應的區間是「左閉右開」的對應的走訪範圍為 $a, a1, \dots, b-1$def for_loop(n: int) - int: for 迴圈 res 0 # 迴圈求和 1, 2, ..., n-1, n for i in range(1, n 1): res i return res上述實作來自 iteration.py同文件還提供了等價的 Java、C、C、Go、Swift、Rust、JavaScript、TypeScript 等多語言版本均位於 zh-hant/codes 目錄下例如 iteration.java、iteration.c。各語言寫法略有差異C/Java 使用for (int i 1; i n; i)的經典三段式寫法Python 則依賴range的開閉區間特性語意等價。上圖展示了該求和函式的流程框圖初始化res 0與計數器i 1判斷i n是否成立成立則執行res i並遞增i否則結束迴圈返回結果。此求和函式的操作數量與輸入資料大小 $n$ 成正比或者說成「線性關係」。實際上時間複雜度描述的就是這個「線性關係」相關內容將在下一節詳細介紹。while 迴圈更自由的迭代形式與for迴圈類似while迴圈也是一種實現迭代的方法。在while迴圈中程式每輪都會先檢查條件如果條件為真則繼續執行否則結束迴圈def while_loop(n: int) - int: while 迴圈 res 0 i 1 # 初始化條件變數 # 迴圈求和 1, 2, ..., n-1, n while i n: res i i 1 # 更新條件變數 return reswhile迴圈比for迴圈的自由度更高在while迴圈中可以自由地設計條件變數的初始化和更新步驟。例如以下程式碼中條件變數i每輪進行兩次更新先1再*2這種情況就不太方便用for迴圈實現def while_loop_ii(n: int) - int: while 迴圈兩次更新 res 0 i 1 # 初始化條件變數 # 迴圈求和 1, 4, 10, ... while i n: res i # 更新條件變數 i 1 i * 2 return res從 iteration.c 可以看到C 語言的whileLoopII與 Python 版本邏輯完全一致印證了「條件變數更新步長由程式設計師自由掌控」的靈活性。總的來說for迴圈的程式碼更加緊湊while迴圈更加靈活兩者都可以實現迭代結構選擇使用哪一個應根據特定問題的需求來決定。巢狀迴圈迭代的「升維」可以在一個迴圈結構內巢狀另一個迴圈結構下面以for迴圈為例def nested_for_loop(n: int) - str: 雙層 for 迴圈 res # 迴圈 i 1, 2, ..., n-1, n for i in range(1, n 1): # 迴圈 j 1, 2, ..., n-1, n for j in range(1, n 1): res f({i}, {j}), return res上圖顯示外層迴圈每執行一輪內層迴圈都要完整走訪 $n$ 次因此總操作次數為 $n \times n$。在這種情況下函式的操作數量與 $n^2$ 成正比或者說演算法執行時間和輸入資料大小 $n$ 成「平方關係」。可以繼續新增巢狀迴圈每一次巢狀都是一次「升維」將會使時間複雜度提高至「立方關係」「四次方關係」以此類推。這是理解 $O(n)$、$O(n^2)$、$O(n^3)$ 時間複雜度最直觀的入口。遞迴函式呼叫自身的演算法策略遞迴是一種演算法策略透過函式呼叫自身來解決問題。它主要包含兩個階段遞程式不斷深入地呼叫自身通常傳入更小或更簡化的參數直到達到「終止條件」。迴觸發「終止條件」後程式從最深層的遞迴函式開始逐層返回匯聚每一層的結果。而從實現的角度看遞迴程式碼主要包含三個要素終止條件用於決定什麼時候由「遞」轉「迴」。遞迴呼叫對應「遞」函式呼叫自身通常輸入更小或更簡化的參數。返回結果對應「迴」將當前遞迴層級的結果返回至上一層。觀察以下程式碼只需呼叫函式recur(n)就可以完成 $1 2 \dots n$ 的計算def recur(n: int) - int: 遞迴 # 終止條件 if n 1: return 1 # 遞遞迴呼叫 res recur(n - 1) # 迴返回結果 return n res該實作對應 recursion.py。值得注意的細節是求和操作n res位於遞迴呼叫之後即它在「迴」的階段才執行——這是普通遞迴的典型特徵也為後文尾遞迴的對比埋下伏筆。等價實作可見 recursion.c 與 recursion.java。兩種解決問題的範式雖然從計算角度看迭代與遞迴可以得到相同的結果但它們代表了兩種完全不同的思考和解決問題的範式迭代「自下而上」地解決問題。從最基礎的步驟開始然後不斷重複或累加這些步驟直到任務完成。遞迴「自上而下」地解決問題。將原問題分解為更小的子問題這些子問題和原問題具有相同的形式。接下來將子問題繼續分解為更小的子問題直到基本情況時停止基本情況的解是已知的。以上述求和函式為例設問題 $f(n) 1 2 \dots n$迭代在迴圈中模擬求和過程從 $1$ 走訪到 $n$每輪執行求和操作即可求得 $f(n)$。遞迴將問題分解為子問題 $f(n) n f(n-1)$不斷遞迴地分解下去直至基本情況 $f(1) 1$ 時終止。呼叫堆疊遞迴的記憶體代價遞迴函式每次呼叫自身時系統都會為新開啟的函式分配記憶體以儲存區域性變數、呼叫位址和其他資訊等。這將導致兩方面的結果函式的上下文資料都儲存在稱為「堆疊幀空間」的記憶體區域中直至函式返回後才會被釋放。因此遞迴通常比迭代更加耗費記憶體空間。遞迴呼叫函式會產生額外的開銷因此遞迴通常比迴圈的時間效率更低。如上圖所示在觸發終止條件前同時存在 $n$ 個未返回的遞迴函式遞迴深度為 $n$。在實際中程式語言允許的遞迴深度通常是有限的過深的遞迴可能導致堆疊溢位錯誤。以 Python 為例預設遞迴深度限制通常為 1000 左右可透過sys.setrecursionlimit調整超過後會拋出RecursionError。尾遞迴空間效率可與迭代相當有趣的是如果函式在返回前的最後一步才進行遞迴呼叫則該函式可以被編譯器或直譯器最佳化使其在空間效率上與迭代相當。這種情況被稱為尾遞迴tail recursion。普通遞迴當函式返回到上一層級的函式後需要繼續執行程式碼因此系統需要儲存上一層呼叫的上下文。尾遞迴遞迴呼叫是函式返回前的最後一個操作這意味著函式返回到上一層級後無須繼續執行其他操作因此系統無須儲存上一層函式的上下文。以計算 $1 2 \dots n$ 為例可以將結果變數res設為函式參數從而實現尾遞迴def tail_recur(n, res): 尾遞迴 # 終止條件 if n 0: return res # 尾遞迴呼叫 return tail_recur(n - 1, res n)注意與普通遞迴的關鍵差異求和操作res n在「遞」的階段就完成了函式的最後一步就是tail_recur(n - 1, res n)這個遞迴呼叫本身返回後不再有任何後續計算。因此在支持尾呼叫最佳化TCO的語言如部分函式式語言中編譯器可以複用當前堆疊幀將空間複雜度從 $O(n)$ 降為 $O(1)$。對比上圖中普通遞迴與尾遞迴的執行過程兩者的求和操作執行點是不同的普通遞迴求和操作是在「迴」的過程中執行的每層返回後都要再執行一次求和操作。尾遞迴求和操作是在「遞」的過程中執行的「迴」的過程只需層層返回。注意許多編譯器或直譯器並不支持尾遞迴最佳化。例如 Python 預設不支持尾遞迴最佳化因此即使函式是尾遞迴形式仍然可能會遇到堆疊溢位問題。遞迴樹費波那契數列與分治思維當處理與「分治」相關的演算法問題時遞迴往往比迭代的思路更加直觀、程式碼更加易讀。以「費波那契數列」為例給定一個費波那契數列 $0, 1, 1, 2, 3, 5, 8, 13, \dots$求該數列的第 $n$ 個數字。設費波那契數列的第 $n$ 個數字為 $f(n)$易得兩個結論數列的前兩個數字為 $f(1) 0$ 和 $f(2) 1$。數列中的每個數字是前兩個數字的和即 $f(n) f(n-1) f(n-2)$。按照遞推關係進行遞迴呼叫將前兩個數字作為終止條件便可寫出遞迴程式碼。呼叫fib(n)即可得到費波那契數列的第 $n$ 個數字def fib(n: int) - int: 費波那契數列遞迴 # 終止條件 f(1) 0, f(2) 1 if n 1 or n 2: return n - 1 # 遞迴呼叫 f(n) f(n-1) f(n-2) res fib(n - 1) fib(n - 2) # 返回結果 f(n) return res觀察以上程式碼在函式內遞迴呼叫了兩個函式這意味著從一個呼叫產生了兩個呼叫分支。如下圖所示這樣不斷遞迴呼叫下去最終將產生一棵層數為 $n$ 的遞迴樹recursion tree從本質上看遞迴體現了「將問題分解為更小子問題」的思維範式這種分治策略至關重要從演算法角度看搜尋、排序、回溯、分治、動態規劃等許多重要演算法策略直接或間接地應用了這種思維方式。從資料結構角度看遞迴天然適合處理鏈結串列、樹和圖的相關問題因為它們非常適合用分治思想進行分析。迭代與遞迴的特點對比總結以上內容如下表所示迭代和遞迴在實現、效能和適用性上有所不同維度迭代遞迴實現方式迴圈結構函式呼叫自身時間效率效率通常較高無函式呼叫開銷每次函式呼叫都會產生開銷記憶體使用通常使用固定大小的記憶體空間累積函式呼叫可能使用大量的堆疊幀空間適用問題適用於簡單迴圈任務程式碼直觀、可讀性好適用於子問題分解如樹、圖、分治、回溯等程式碼結構簡潔、清晰內在關聯用堆疊模擬遞迴如果感覺以下內容理解困難可以在讀完「堆疊」章節後再來複習。迭代和遞迴具有什麼內在關聯呢以上述遞迴函式為例求和操作在遞迴的「迴」階段進行。這意味著最初被呼叫的函式實際上是最後完成其求和操作的這種工作機制與堆疊的「先入後出」原則異曲同工。事實上「呼叫堆疊」和「堆疊幀空間」這類遞迴術語已經暗示了遞迴與堆疊之間的密切關係遞當函式被呼叫時系統會在「呼叫堆疊」上為該函式分配新的堆疊幀用於儲存函式的區域性變數、參數、返回位址等資料。迴當函式完成執行並返回時對應的堆疊幀會被從「呼叫堆疊」上移除恢復之前函式的執行環境。因此可以使用一個顯式的堆疊來模擬呼叫堆疊的行為從而將遞迴轉化為迭代形式def for_loop_recur(n: int) - int: 使用迭代模擬遞迴 # 使用一個顯式的堆疊來模擬系統呼叫堆疊 stack [] res 0 # 遞遞迴呼叫 for i in range(n, 0, -1): # 透過「入堆疊操作」模擬「遞」 stack.append(i) # 迴返回結果 while stack: # 透過「出堆疊操作」模擬「迴」 res stack.pop() # res 123...n return res該實作在 recursion.py 中使用 Python 內建list充當堆疊Java 版本則直接使用標準庫的StackInteger見 recursion.java而 C 版本出於效能考量用一個大陣列手動維護堆疊頂索引top見 recursion.c三種實作揭示了「堆疊抽象」在不同語言中的落地方式。觀察以上程式碼當遞迴轉化為迭代後程式碼變得更加複雜了。儘管迭代和遞迴在很多情況下可以互相轉化但不一定值得這樣做有以下兩點原因轉化後的程式碼可能更加難以理解可讀性更差。對於某些複雜問題模擬系統呼叫堆疊的行為可能非常困難。總之選擇迭代還是遞迴取決於特定問題的性質。在程式設計實踐中權衡兩者的優劣並根據情境選擇合適的方法至關重要。建議讀者在本章學習完時間複雜度與空間複雜度後再回到本文重新審視for_loop與recur的差異屆時對「線性關係」「堆疊幀空間」「遞迴深度」等概念將有更深刻的體會。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考