尧图网站建设 
Hello 算法迭代與遞迴的逐步可視化 —— 從 Python Tutor 程式碼走查看懂迴圈與遞迴的複雜度【免费下载链接】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 算法》繁體中文版「計算複雜度」章節的互動可視化文件iteration.md為主體逐個拆解其中內嵌的 8 段程式範例for迴圈、while迴圈、雙層迴圈、基本遞迴、尾遞迴、費波那契數列以及「用迭代模擬遞迴」。讀完後你將掌握兩種基本控制結構的寫法差異、如何用 Python Tutor 逐步觀察變數與呼叫堆疊的演變並能從程式碼結構直接推斷出對應的時間複雜度量級。這份可視化文件是什麼一頁一份「逐步走查」清單zh-hant/codes/pythontutor/chapter_computational_complexity/目錄下的 pythontutor 系列檔案是《Hello 算法》為每個章節的關鍵程式範例預先準備的互動式逐步執行走查入口。以本次的 iteration.md 為例它的組織方式非常規律每個段落以註解標記來源例如!-- [file]{iteration}-[class]{}-[func]{for_loop} --表示下面的可視化內容取自iteration.py中的for_loop()函式每段附一條pythontutor.com/render.html#code...的完整連結程式碼已直接內嵌在 URL 參數中開啟即可看到對應函式的原始碼與執行環境檔案中的 8 條走查連結分別覆蓋 4 個迭代範例取自 iteration.py與 4 個遞迴範例取自 recursion.py與章節講義 iteration_and_recursion.md 的「迭代」與「遞迴」兩節一一對應。從這份可視化清單的 URL 參數可以看出 Python Tutor 的執行配置py311代表使用 Python 3.11 語法modedisplay是圖形化逐幀展示模式curInstr3表示初始暫停在程式的第 3 個執行步驟heapPrimitivesnevernest控制物件以堆疊而非巢狀方式顯示cumulativefalse則決定是否累積顯示已走訪過的幀。換句話說只要打開該檔案中的任意一條連結就能一鍵載入對應範例並逐步執行這是與靜態閱讀最大的不同。下表是本文會逐一講解的 8 個可視化範例總覽來源檔案函式主題對應講義小節iteration.pyfor_loop()for迴圈求和迭代iteration.pywhile_loop()while迴圈求和迭代iteration.pywhile_loop_ii()while迴圈兩次更新條件變數迭代iteration.pynested_for_loop()雙層for迴圈迭代recursion.pyrecur()基本遞迴求和遞迴recursion.pytail_recur()尾遞迴遞迴recursion.pyfib()費波那契數列多重遞迴遞迴recursion.pyfor_loop_recur()用顯式堆疊模擬遞迴遞迴與迭代的關聯先建立座標迭代是「自下而上」遞迴是「自上而下」在逐段走查程式之前先明確兩者的本質差異。根據講義 iteration_and_recursion.md 的歸納迭代iteration一種重複執行某段任務的控制結構程式在條件滿足時反覆執行同一段程式碼直到條件不再成立。它「自下而上」地解決問題——從最基礎的步驟開始不斷重複或累加直到任務完成遞迴recursion透過函式呼叫自身來實現重複可理解為「自上而下」地將大問題拆成同構的小問題再由小問題的解組裝回大問題的解。另外要牢記兩點性能前提其一遞迴時函式的上下文資料會存放在稱為「棧幀空間」stack frame的記憶體區塊直到函式返回才被釋放因此遞迴通常比迭代更耗記憶體其二若函式在返回前的最後一步才進行遞迴呼叫即所謂尾遞迴tail recursion則可能被編譯器或直譯器優化使其空間效率與迭代相當。下面的可視化走查會反覆驗證這些結論。迭代家族走查一for迴圈for迴圈是最常見的迭代形式適合在預先知道迭代次數時使用。可視化文件的第一條連結對應 iteration.py 中的for_loop()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用 Python Tutor 逐步執行時可以觀察到兩個變數的變化i依次取值1, 2, ..., nrange(1, n 1)是左閉右開區間因此寫成n 1累加器res每一輪都增加當前的i。當驅動程式以n 5呼叫時見同檔案的 Driver Codeiteration.py迴圈結束後res 1 2 3 4 5 15。從程式碼結構可以直接推斷複雜度迴圈需要執行恰好n輪每輪只做常數次運算故時間複雜度為O(n)整個過程只用了res、i兩個變數空間複雜度為O(1)。迭代家族走查二while迴圈第二條連結對應while_loop()iteration.py。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 res逐幀走查時請特別留意i的角色它在迴圈外被初始化為1每輪末尾執行i 1向終止條件i n逼近。若漏寫這一步更新條件永遠為真就會形成無窮迴圈——這正是 Python Tutor 逐步執行最適合用來「親眼看見」的風險點。比較兩種寫法可以總結for迴圈把「迭代變數的產生」封裝在range()之中程式碼更緊湊while迴圈把初始化、條件判斷與更新完全攤開更具彈性能表達更複雜的更新規則。時間與空間複雜度與for_loop()相同均為 O(n) 時間、O(1) 空間。迭代家族走查三while迴圈的兩次更新while迴圈的彈性在第三個範例中體現得淋漓盡致。while_loop_ii()iteration.py在每一輪對條件變數i同時做i 1與i * 2兩次更新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 resi的取值序列為1, 4, 10, 22, ...每輪先加 1 再翻倍近似翻倍增長因此以n 5執行時迴圈只會跑 3 輪i 1、i 4、i 10第 4 輪檢查時i已超過n。若取較大的n從程式碼結構可以推斷條件變數以接近指數速度增長能到達n的輪數只有O(log n)量級——時間複雜度從 O(n) 降到了 O(log n)這是「控制迭代步長」直接改變複雜度的經典示範也正是while迴圈比for迴圈靈活的體現。由於只使用常數個變數空間複雜度仍為 O(1)。迭代家族走查四雙層for迴圈第四個範例nested_for_loop()iteration.py示範迴圈的嵌套組合逐一產生所有座標對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雙層迴圈對每一組(i, j)執行一次內層操作i與j各遍歷n個值因此總操作次數為n × n時間複雜度為O(n²)。以n 5執行時輸出(1, 1), (1, 2), ..., (5, 5)共 25 個座標對。注意此處函式返回型別為str累加的對象是字串與前面幾個求和的整數累加不同——在 Python Tutor 中可以看到res的型別與內容隨之改變這是觀察「累加器型別隨運算子而定」的好機會。嵌套層數每增加一層時間複雜度通常就再乘上一個n這也為後續「時間複雜度」章節中 O(n²)、O(n³) 的理解打下直觀基礎。遞迴走查一基本遞迴遞與迴第五條連結開始進入遞迴範例來源切換為 recursion.py對應 pythontutor 檔案中的[file]{recursion}註記。recur()recursion.py是理解遞迴的最佳起點def recur(n: int) - int: 遞迴 # 終止條件 if n 1: return 1 # 遞遞迴呼叫 res recur(n - 1) # 迴返回結果 return n res一個遞迴函式必須具備兩個要素終止條件此處為n 1與遞迴呼叫。recur的名字本身就點明了執行過程的兩個階段「遞」以recur(5)為例函式依序呼叫recur(4)、recur(3)、recur(2)、recur(1)每次呼叫都會在系統呼叫堆疊上疊起一個新的棧幀保存各自的參數n「迴」直到recur(1)命中終止條件返回1呼叫開始逐層彈出棧幀recur(2)返回2 1 3recur(3)返回3 3 6依此類推最終recur(5)返回15。在 Python Tutor 中執行這個範例是觀察「棧幀空間」與「呼叫堆疊」最直觀的方式點擊「下一步」時畫面左側會清楚列出當前同時存在的每一層recur呼叫及其n值——這正是前面提到的「遞迴比迭代耗費更多記憶體」的視覺證據。求和操作發生在「迴」的階段這意味著最早被呼叫的函式反而是最後完成求和的這種「先入後出」的工作機制與棧的原則如出一轍。時間複雜度為 O(n)共n - 1次遞迴呼叫但由於呼叫堆疊深度同樣為 O(n)其空間複雜度為O(n)——與迭代版的 O(1) 空間形成鮮明對比。遞迴走查二尾遞迴第六個範例tail_recur()recursion.py展示尾遞迴的寫法def tail_recur(n, res): 尾遞迴 # 終止條件 if n 0: return res # 尾遞迴呼叫 return tail_recur(n - 1, res n)與recur()的關鍵差異在於遞迴呼叫是函式返回前的最後一個操作處於「尾」部且計算結果透過參數res一路向下傳遞而不是在「迴」的階段才做加法。以tail_recur(5, 0)為例呼叫鏈為tail_recur(5, 0) → tail_recur(4, 5) → tail_recur(3, 9) → ... → tail_recur(0, 15)一旦n歸零直接返回累積好的res 15不再需要逐層回溯做運算。在 Python Tutor 中觀察兩者的差別非常明顯recur()的加法發生在「返回的路上」每一層棧幀都得保留著等下面的結果回來而tail_recur()的每一層棧幀把結果算完就沒有「回頭運算」了。正因如此講義指出若語言支援尾呼叫優化尾遞迴可以讓函式在空間效率上與迭代相當——當然需要說明的是具體能否優化取決於執行環境這並不改變它在 Python Tutor 中呈現出的呼叫鏈形態。時間複雜度同樣為 O(n)。遞迴走查三費波那契數列多重遞迴分支第七個範例fib()recursion.py展示一個函式在單次呼叫中發起兩條遞迴分支的情形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此處終止條件定義了f(1) 0、f(2) 1一般項滿足f(n) f(n-1) f(n-2)。以n 5為例fib(5)會同時需要fib(4)與fib(3)而這兩者又各自展開……整個計算形成一棵遞迴呼叫樹。在 Python Tutor 中這是最「壯觀」也最值得觀察的一幀右側的呼叫堆疊會同時存在多條尚未返回的fib分支。從呼叫樹的結構可以推斷其成本——樹中每個節點代表一次呼叫而樹的規模隨n指數成長時間複雜度為O(2^n)量級。這正是「多重遞迴導致大量重複計算」的典型反面教材也為日後在動態規劃章節中用記憶化搜尋或 DP 表格將指數級暴力遞迴優化為多項式級演算法埋下了強烈的動機。遞迴走查四用顯式堆疊把遞迴「翻譯」成迭代最後一條走查連結對應for_loop_recur()recursion.py。正如前面所述遞迴依賴系統呼叫堆疊的「先入後出」而棧這種資料結構在《Hello 算法》的「堆疊」章節已有完整實現——因此我們可以建立一個顯式explicit的堆疊來模擬呼叫堆疊的行為把遞迴改寫成迭代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這段程式碼把遞迴的兩個階段「演」給你看先以for i in range(n, 0, -1)把n, n-1, ..., 1依序入堆疊模擬「遞」階段的逐層呼叫注意入堆疊順序刻意與呼叫順序相反才能讓最小參數在棧頂再用while stack迴圈不斷pop()出棧頂並累加模擬「迴」階段的逐層返回。執行結果與recur(n)完全一致都是1 2 ... n。在 Python Tutor 中走查這個範例可以看到「呼叫堆疊」被替換成了使用者資料中的一個list物件棧幀的漲落變成了一目了然的入棧、出棧動畫。這同時也說明了一個重要的工程判斷遞迴與迭代在很多情況下可以互相轉化但不一定值得做。正如講義所提醒的——改寫後程式碼往往變得更複雜需要自行管理堆疊、處理狀態保存。所以實踐中的原則是以問題性質為依據選擇迭代或遞迴若問題具有清晰的分治結構如後續章節的樹走訪、回溯演算法遞迴通常更直觀、更不易出錯若追求極致的空間效率或避免過深呼叫堆疊才考慮迭代化。在專案中實際執行與驗證上述 8 個函式全部收錄在兩份可直接執行的 Python 原始檔中且都帶有Driver Code可一鍵執行驗證輸出迭代範例iteration.py運行後依次輸出for 迴圈的求和結果 res 15、while 迴圈的求和結果 res 15、while 迴圈兩次更新求和結果 res 15注n 5時三種求和的res恰好同為 15但中間迭代軌跡不同可在 Python Tutor 中對比觀察以及雙層迴圈輸出的 25 個座標對遞迴範例recursion.py運行後輸出recur、for_loop_recur、tail_recur三個求和的res 15以及費波那契數列第 5 項res 3。在安裝了 Python 3 的環境中先進入原始檔所在目錄再執行python3 iteration.py或python3 recursion.py即可看到全部輸出。若要對照完整理論講解含迭代與遞迴的特點對比表、呼叫堆疊示意圖可閱讀章節講義 iteration_and_recursion.md該章節在「時間複雜度」「空間複雜度」兩個子題中分別討論了這些迴圈結構的漸進分析。最後建議的學習路線是「三步走」第一步用本指南走查 iteration.md 中每一條 Python Tutor 連結把 8 個範例的變數與堆疊變化看在眼裡第二步回到 iteration.py 與 recursion.py 自行修改n的數值並運行驗證複雜度隨輸入規模的變化趨勢第三步帶著對迭代與遞迴的直觀理解進入《Hello 算法》接下來的複雜度分析章節將 O(n)、O(log n)、O(n²)、O(2^n) 這些符號與你在視覺化中親眼看到的執行軌跡一一對應起來。【免费下载链接】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），仅供参考 Hello 算法：迭代與遞迴的逐步可視化 —— 從 Python Tutor 程式碼走查看懂迴圈與遞迴的複雜度
Hello 算法迭代與遞迴的逐步可視化 —— 從 Python Tutor 程式碼走查看懂迴圈與遞迴的複雜度【免费下载链接】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 算法》繁體中文版「計算複雜度」章節的互動可視化文件iteration.md為主體逐個拆解其中內嵌的 8 段程式範例for迴圈、while迴圈、雙層迴圈、基本遞迴、尾遞迴、費波那契數列以及「用迭代模擬遞迴」。讀完後你將掌握兩種基本控制結構的寫法差異、如何用 Python Tutor 逐步觀察變數與呼叫堆疊的演變並能從程式碼結構直接推斷出對應的時間複雜度量級。這份可視化文件是什麼一頁一份「逐步走查」清單zh-hant/codes/pythontutor/chapter_computational_complexity/目錄下的 pythontutor 系列檔案是《Hello 算法》為每個章節的關鍵程式範例預先準備的互動式逐步執行走查入口。以本次的 iteration.md 為例它的組織方式非常規律每個段落以註解標記來源例如!-- [file]{iteration}-[class]{}-[func]{for_loop} --表示下面的可視化內容取自iteration.py中的for_loop()函式每段附一條pythontutor.com/render.html#code...的完整連結程式碼已直接內嵌在 URL 參數中開啟即可看到對應函式的原始碼與執行環境檔案中的 8 條走查連結分別覆蓋 4 個迭代範例取自 iteration.py與 4 個遞迴範例取自 recursion.py與章節講義 iteration_and_recursion.md 的「迭代」與「遞迴」兩節一一對應。從這份可視化清單的 URL 參數可以看出 Python Tutor 的執行配置py311代表使用 Python 3.11 語法modedisplay是圖形化逐幀展示模式curInstr3表示初始暫停在程式的第 3 個執行步驟heapPrimitivesnevernest控制物件以堆疊而非巢狀方式顯示cumulativefalse則決定是否累積顯示已走訪過的幀。換句話說只要打開該檔案中的任意一條連結就能一鍵載入對應範例並逐步執行這是與靜態閱讀最大的不同。下表是本文會逐一講解的 8 個可視化範例總覽來源檔案函式主題對應講義小節iteration.pyfor_loop()for迴圈求和迭代iteration.pywhile_loop()while迴圈求和迭代iteration.pywhile_loop_ii()while迴圈兩次更新條件變數迭代iteration.pynested_for_loop()雙層for迴圈迭代recursion.pyrecur()基本遞迴求和遞迴recursion.pytail_recur()尾遞迴遞迴recursion.pyfib()費波那契數列多重遞迴遞迴recursion.pyfor_loop_recur()用顯式堆疊模擬遞迴遞迴與迭代的關聯先建立座標迭代是「自下而上」遞迴是「自上而下」在逐段走查程式之前先明確兩者的本質差異。根據講義 iteration_and_recursion.md 的歸納迭代iteration一種重複執行某段任務的控制結構程式在條件滿足時反覆執行同一段程式碼直到條件不再成立。它「自下而上」地解決問題——從最基礎的步驟開始不斷重複或累加直到任務完成遞迴recursion透過函式呼叫自身來實現重複可理解為「自上而下」地將大問題拆成同構的小問題再由小問題的解組裝回大問題的解。另外要牢記兩點性能前提其一遞迴時函式的上下文資料會存放在稱為「棧幀空間」stack frame的記憶體區塊直到函式返回才被釋放因此遞迴通常比迭代更耗記憶體其二若函式在返回前的最後一步才進行遞迴呼叫即所謂尾遞迴tail recursion則可能被編譯器或直譯器優化使其空間效率與迭代相當。下面的可視化走查會反覆驗證這些結論。迭代家族走查一for迴圈for迴圈是最常見的迭代形式適合在預先知道迭代次數時使用。可視化文件的第一條連結對應 iteration.py 中的for_loop()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用 Python Tutor 逐步執行時可以觀察到兩個變數的變化i依次取值1, 2, ..., nrange(1, n 1)是左閉右開區間因此寫成n 1累加器res每一輪都增加當前的i。當驅動程式以n 5呼叫時見同檔案的 Driver Codeiteration.py迴圈結束後res 1 2 3 4 5 15。從程式碼結構可以直接推斷複雜度迴圈需要執行恰好n輪每輪只做常數次運算故時間複雜度為O(n)整個過程只用了res、i兩個變數空間複雜度為O(1)。迭代家族走查二while迴圈第二條連結對應while_loop()iteration.py。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 res逐幀走查時請特別留意i的角色它在迴圈外被初始化為1每輪末尾執行i 1向終止條件i n逼近。若漏寫這一步更新條件永遠為真就會形成無窮迴圈——這正是 Python Tutor 逐步執行最適合用來「親眼看見」的風險點。比較兩種寫法可以總結for迴圈把「迭代變數的產生」封裝在range()之中程式碼更緊湊while迴圈把初始化、條件判斷與更新完全攤開更具彈性能表達更複雜的更新規則。時間與空間複雜度與for_loop()相同均為 O(n) 時間、O(1) 空間。迭代家族走查三while迴圈的兩次更新while迴圈的彈性在第三個範例中體現得淋漓盡致。while_loop_ii()iteration.py在每一輪對條件變數i同時做i 1與i * 2兩次更新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 resi的取值序列為1, 4, 10, 22, ...每輪先加 1 再翻倍近似翻倍增長因此以n 5執行時迴圈只會跑 3 輪i 1、i 4、i 10第 4 輪檢查時i已超過n。若取較大的n從程式碼結構可以推斷條件變數以接近指數速度增長能到達n的輪數只有O(log n)量級——時間複雜度從 O(n) 降到了 O(log n)這是「控制迭代步長」直接改變複雜度的經典示範也正是while迴圈比for迴圈靈活的體現。由於只使用常數個變數空間複雜度仍為 O(1)。迭代家族走查四雙層for迴圈第四個範例nested_for_loop()iteration.py示範迴圈的嵌套組合逐一產生所有座標對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雙層迴圈對每一組(i, j)執行一次內層操作i與j各遍歷n個值因此總操作次數為n × n時間複雜度為O(n²)。以n 5執行時輸出(1, 1), (1, 2), ..., (5, 5)共 25 個座標對。注意此處函式返回型別為str累加的對象是字串與前面幾個求和的整數累加不同——在 Python Tutor 中可以看到res的型別與內容隨之改變這是觀察「累加器型別隨運算子而定」的好機會。嵌套層數每增加一層時間複雜度通常就再乘上一個n這也為後續「時間複雜度」章節中 O(n²)、O(n³) 的理解打下直觀基礎。遞迴走查一基本遞迴遞與迴第五條連結開始進入遞迴範例來源切換為 recursion.py對應 pythontutor 檔案中的[file]{recursion}註記。recur()recursion.py是理解遞迴的最佳起點def recur(n: int) - int: 遞迴 # 終止條件 if n 1: return 1 # 遞遞迴呼叫 res recur(n - 1) # 迴返回結果 return n res一個遞迴函式必須具備兩個要素終止條件此處為n 1與遞迴呼叫。recur的名字本身就點明了執行過程的兩個階段「遞」以recur(5)為例函式依序呼叫recur(4)、recur(3)、recur(2)、recur(1)每次呼叫都會在系統呼叫堆疊上疊起一個新的棧幀保存各自的參數n「迴」直到recur(1)命中終止條件返回1呼叫開始逐層彈出棧幀recur(2)返回2 1 3recur(3)返回3 3 6依此類推最終recur(5)返回15。在 Python Tutor 中執行這個範例是觀察「棧幀空間」與「呼叫堆疊」最直觀的方式點擊「下一步」時畫面左側會清楚列出當前同時存在的每一層recur呼叫及其n值——這正是前面提到的「遞迴比迭代耗費更多記憶體」的視覺證據。求和操作發生在「迴」的階段這意味著最早被呼叫的函式反而是最後完成求和的這種「先入後出」的工作機制與棧的原則如出一轍。時間複雜度為 O(n)共n - 1次遞迴呼叫但由於呼叫堆疊深度同樣為 O(n)其空間複雜度為O(n)——與迭代版的 O(1) 空間形成鮮明對比。遞迴走查二尾遞迴第六個範例tail_recur()recursion.py展示尾遞迴的寫法def tail_recur(n, res): 尾遞迴 # 終止條件 if n 0: return res # 尾遞迴呼叫 return tail_recur(n - 1, res n)與recur()的關鍵差異在於遞迴呼叫是函式返回前的最後一個操作處於「尾」部且計算結果透過參數res一路向下傳遞而不是在「迴」的階段才做加法。以tail_recur(5, 0)為例呼叫鏈為tail_recur(5, 0) → tail_recur(4, 5) → tail_recur(3, 9) → ... → tail_recur(0, 15)一旦n歸零直接返回累積好的res 15不再需要逐層回溯做運算。在 Python Tutor 中觀察兩者的差別非常明顯recur()的加法發生在「返回的路上」每一層棧幀都得保留著等下面的結果回來而tail_recur()的每一層棧幀把結果算完就沒有「回頭運算」了。正因如此講義指出若語言支援尾呼叫優化尾遞迴可以讓函式在空間效率上與迭代相當——當然需要說明的是具體能否優化取決於執行環境這並不改變它在 Python Tutor 中呈現出的呼叫鏈形態。時間複雜度同樣為 O(n)。遞迴走查三費波那契數列多重遞迴分支第七個範例fib()recursion.py展示一個函式在單次呼叫中發起兩條遞迴分支的情形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此處終止條件定義了f(1) 0、f(2) 1一般項滿足f(n) f(n-1) f(n-2)。以n 5為例fib(5)會同時需要fib(4)與fib(3)而這兩者又各自展開……整個計算形成一棵遞迴呼叫樹。在 Python Tutor 中這是最「壯觀」也最值得觀察的一幀右側的呼叫堆疊會同時存在多條尚未返回的fib分支。從呼叫樹的結構可以推斷其成本——樹中每個節點代表一次呼叫而樹的規模隨n指數成長時間複雜度為O(2^n)量級。這正是「多重遞迴導致大量重複計算」的典型反面教材也為日後在動態規劃章節中用記憶化搜尋或 DP 表格將指數級暴力遞迴優化為多項式級演算法埋下了強烈的動機。遞迴走查四用顯式堆疊把遞迴「翻譯」成迭代最後一條走查連結對應for_loop_recur()recursion.py。正如前面所述遞迴依賴系統呼叫堆疊的「先入後出」而棧這種資料結構在《Hello 算法》的「堆疊」章節已有完整實現——因此我們可以建立一個顯式explicit的堆疊來模擬呼叫堆疊的行為把遞迴改寫成迭代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這段程式碼把遞迴的兩個階段「演」給你看先以for i in range(n, 0, -1)把n, n-1, ..., 1依序入堆疊模擬「遞」階段的逐層呼叫注意入堆疊順序刻意與呼叫順序相反才能讓最小參數在棧頂再用while stack迴圈不斷pop()出棧頂並累加模擬「迴」階段的逐層返回。執行結果與recur(n)完全一致都是1 2 ... n。在 Python Tutor 中走查這個範例可以看到「呼叫堆疊」被替換成了使用者資料中的一個list物件棧幀的漲落變成了一目了然的入棧、出棧動畫。這同時也說明了一個重要的工程判斷遞迴與迭代在很多情況下可以互相轉化但不一定值得做。正如講義所提醒的——改寫後程式碼往往變得更複雜需要自行管理堆疊、處理狀態保存。所以實踐中的原則是以問題性質為依據選擇迭代或遞迴若問題具有清晰的分治結構如後續章節的樹走訪、回溯演算法遞迴通常更直觀、更不易出錯若追求極致的空間效率或避免過深呼叫堆疊才考慮迭代化。在專案中實際執行與驗證上述 8 個函式全部收錄在兩份可直接執行的 Python 原始檔中且都帶有Driver Code可一鍵執行驗證輸出迭代範例iteration.py運行後依次輸出for 迴圈的求和結果 res 15、while 迴圈的求和結果 res 15、while 迴圈兩次更新求和結果 res 15注n 5時三種求和的res恰好同為 15但中間迭代軌跡不同可在 Python Tutor 中對比觀察以及雙層迴圈輸出的 25 個座標對遞迴範例recursion.py運行後輸出recur、for_loop_recur、tail_recur三個求和的res 15以及費波那契數列第 5 項res 3。在安裝了 Python 3 的環境中先進入原始檔所在目錄再執行python3 iteration.py或python3 recursion.py即可看到全部輸出。若要對照完整理論講解含迭代與遞迴的特點對比表、呼叫堆疊示意圖可閱讀章節講義 iteration_and_recursion.md該章節在「時間複雜度」「空間複雜度」兩個子題中分別討論了這些迴圈結構的漸進分析。最後建議的學習路線是「三步走」第一步用本指南走查 iteration.md 中每一條 Python Tutor 連結把 8 個範例的變數與堆疊變化看在眼裡第二步回到 iteration.py 與 recursion.py 自行修改n的數值並運行驗證複雜度隨輸入規模的變化趨勢第三步帶著對迭代與遞迴的直觀理解進入《Hello 算法》接下來的複雜度分析章節將 O(n)、O(log n)、O(n²)、O(2^n) 這些符號與你在視覺化中親眼看到的執行軌跡一一對應起來。【免费下载链接】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），仅供参考