遞歸一個(gè)在編程入門階段必講、但很多人到工作兩三年后依然說不清的概念。網(wǎng)上講遞歸的文章一大把大部分都在強(qiáng)調(diào)遞過去、歸回來這六個(gè)字可你會(huì)背這六個(gè)字照樣寫不出一個(gè)像樣的遞歸函數(shù)。我這篇不打算重復(fù)那套說教我想把遞歸這件事拆到不能再細(xì)函數(shù)調(diào)用棧到底是什么、遞歸運(yùn)行時(shí)發(fā)生了什么、經(jīng)典的快速排序遞歸怎么寫、怎么一步步改成非遞歸以及面試和實(shí)戰(zhàn)里最常踩的坑?？赐赀@一篇遞歸和快排非遞歸這些問題你基本就能在心里一次性理清。這篇內(nèi)容的定位是給兩種人看一是剛學(xué)完編程基礎(chǔ)、被遞歸折騰得頭疼的新人二是自認(rèn)為會(huì)用遞歸、但說不太清底層原理、遇到棧溢出只能靠加遞歸深度上限糊弄過去的開發(fā)者。兩種人都會(huì)在下面找到自己需要的東西——前者的重點(diǎn)在理解模型和執(zhí)行過程后者的重點(diǎn)在快排非遞歸的完整落地和通用改寫方法論。1. 為什么遞歸總是一看就懂一寫就廢1.1 遞歸的本質(zhì)不是自己調(diào)用自己這么簡(jiǎn)單很多人對(duì)遞歸的理解停留在函數(shù)在函數(shù)體里調(diào)用自己。這句話對(duì)但沒有解釋任何東西。遞歸的真正本質(zhì)是一個(gè)大問題被分解成若干個(gè)結(jié)構(gòu)完全相同的更小問題直到小到可以直接給出答案為止。拿俄羅斯套娃來類比一個(gè)套娃打開里面是一個(gè)更小的套娃再打開又是一個(gè)更小的套娃直到最小的那個(gè)實(shí)心套娃無(wú)法再打開。你要數(shù)清總共有幾個(gè)套娃做法就是打開一個(gè)數(shù) 1然后重復(fù)同樣的動(dòng)作去處理里面那個(gè)更小的。遞歸函數(shù)做的就是這個(gè)事情。更重要的是遞歸函數(shù)其實(shí)每次調(diào)用自己時(shí)每次使用的都是同一個(gè)函數(shù)代碼但每次擁有獨(dú)立的變量空間。這一點(diǎn)必須刻進(jìn)腦子里否則后面讀遞歸執(zhí)行過程必暈。1.2 遞歸三要素終止條件、遞推關(guān)系、縮小規(guī)模我寫遞歸的時(shí)候會(huì)在腦子里強(qiáng)制過三關(guān)終止條件base case問題小到什么程度時(shí)我可以直接返回答案不再繼續(xù)調(diào)用遞推關(guān)系recursive relation當(dāng)前問題的答案怎么由更小規(guī)模問題的答案組裝出來規(guī)模縮小progress每次遞歸調(diào)用參數(shù)是否嚴(yán)格向著終止條件靠近這三個(gè)要素缺一不可。缺了終止條件函數(shù)無(wú)限調(diào)用直接把調(diào)用棧撐爆遞推關(guān)系寫錯(cuò)返回結(jié)果牛頭不對(duì)馬嘴規(guī)模沒縮小其實(shí)就是缺少終止條件的另一種表現(xiàn)本質(zhì)上還是死循環(huán)遞歸。一個(gè)最經(jīng)典的例子計(jì)算階乘 n!def factorial(n): # 終止條件 if n 1: return 1 # 遞推關(guān)系n! n * (n-1)! return n * factorial(n - 1)這里n - 1就是規(guī)模縮小n 1就是終止條件n * factorial(n - 1)就是遞推關(guān)系。函數(shù)本身只有短短幾行但它的執(zhí)行過程值得拆開來看這就是下一章要做的事。2. 拆解遞歸的執(zhí)行過程從棧幀到調(diào)用棧2.1 遞歸函數(shù)進(jìn)入和退出的完整流程很多教材會(huì)告訴你調(diào)用棧這個(gè)概念但你真正理解它是看一場(chǎng)完整的調(diào)用流程之后。以factorial(4)為例我一步步寫給你看。第一次調(diào)用factorial(4)時(shí)系統(tǒng)在調(diào)用棧上壓入一個(gè)棧幀棧幀里保存了參數(shù)n 4、返回地址、局部變量等信息。進(jìn)入函數(shù)體后發(fā)現(xiàn)n ! 1于是執(zhí)行4 * factorial(3)。注意先要計(jì)算factorial(3)才能乘 4所以factorial(4)的棧幀不能彈出必須留在棧里等著。于是系統(tǒng)壓入第二個(gè)棧幀參數(shù)n 3。同樣的邏輯又壓入第三個(gè)棧幀n 2再壓入第四個(gè)棧幀n 1。當(dāng)n 1這個(gè)棧幀執(zhí)行時(shí)命中終止條件直接返回 1這個(gè)棧幀彈出。返回值交給上一層的factorial(2)它計(jì)算2 * 1 2彈出自己的棧幀。返回值再交給factorial(3)計(jì)算3 * 2 6。再交給factorial(4)計(jì)算4 * 6 24彈出最后一個(gè)棧幀。所以整個(gè)調(diào)用棧的過程是factorial(4) |- factorial(3) | |- factorial(2) | | |- factorial(1) | | | 返回 1 | | 返回 2 * 1 2 | 返回 3 * 2 6 返回 4 * 6 24這個(gè)縮進(jìn)圖你一定要自己動(dòng)手畫一遍。畫完你會(huì)發(fā)現(xiàn)遞歸的遞就是逐層壓棧歸就是逐層彈棧并計(jì)算結(jié)果。整個(gè)過程和函數(shù) A 調(diào)用函數(shù) B函數(shù) B 調(diào)用函數(shù) C沒有任何本質(zhì)區(qū)別只不過 A、B、C 恰好都是同一個(gè)函數(shù)而已。2.2 棧溢出的成因與遞歸深度的工程邊界既然遞歸只是壓棧彈棧那棧溢出就不難理解了每次調(diào)用壓入一個(gè)棧幀如果遞歸深度太大調(diào)用棧的空間被耗盡程序就被迫終止。Python 里默認(rèn)的遞歸深度限制通常是 1000 左右超過就會(huì)拋出RecursionError。有人試圖用sys.setrecursionlimit(1000000)把限制調(diào)大然后繼續(xù)跑深遞歸。這樣做在測(cè)試環(huán)境偶爾能撐住但生產(chǎn)環(huán)境我不建議你這么玩。原因有兩個(gè)棧空間是有限的調(diào)高限制只是推遲崩潰而且容易導(dǎo)致進(jìn)程直接段錯(cuò)誤segmentation fault而不是給你一個(gè)優(yōu)雅的 Python 異常。深遞歸本身的性能也很差每一次函數(shù)調(diào)用都有額外的開銷壓棧、彈棧、參數(shù)拷貝、返回地址維護(hù)。所以遞歸深度這道坎不是改參數(shù)能繞過去的要么換非遞歸寫法要么用尾遞歸優(yōu)化要么用動(dòng)態(tài)規(guī)劃自底向上改。后面講快排非遞歸時(shí)你會(huì)看到我們是怎么繞開這道坎的。3. 遞歸實(shí)戰(zhàn)套路從斐波那契到全排列建立分而治之的腦回路3.1 斐波那契數(shù)列的遞歸實(shí)現(xiàn)與性能陷阱斐波那契數(shù)列是遞歸教科書必講案例def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)代碼極短可讀性極好但它有一個(gè)嚴(yán)重問題重復(fù)計(jì)算。當(dāng)n 5時(shí)調(diào)用fib(4)和fib(3)。而fib(4)又會(huì)調(diào)用fib(3)和fib(2)。這里的fib(3)被計(jì)算了兩次fib(2)被計(jì)算了三次。隨著n增大重復(fù)調(diào)用是指數(shù)級(jí)增長(zhǎng)的復(fù)雜度大約 O(2^n)。fib(40)就已經(jīng)慢得肉眼可見fib(50)在普通機(jī)器上可能要跑很久。解決思路有兩個(gè)加緩存做備忘錄memoization或者改成循環(huán)遞推。備忘錄版本def fib_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 1: return n memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo) return memo[n]循環(huán)遞推版本def fib_iter(n): if n 1: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b return b這里我想說一個(gè)觀點(diǎn)遞歸不是用來炫技的它是用來讓代碼與問題本身的結(jié)構(gòu)對(duì)齊。斐波那契的數(shù)學(xué)定義本身就是遞推的所以遞歸寫法天然匹配定義但工程上我們還是會(huì)優(yōu)先選循環(huán)版本。3.2 全排列的遞歸思維回溯的雛形全排列是另一個(gè)經(jīng)典題目給你一個(gè)數(shù)組[1, 2, 3]輸出所有排列。它的遞歸寫法特別能體現(xiàn)狀態(tài)選擇的思想。def permute(nums): result [] used [False] * len(nums) path [] def backtrack(): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack() used[i] False path.pop() backtrack() return result這里的關(guān)鍵不是看代碼本身而是體會(huì)遞歸內(nèi)的選擇-遞歸-撤銷選擇這個(gè)循環(huán)。path.append就是選擇backtrack()就是進(jìn)入更深的決策層path.pop()和used[i] False就是回溯復(fù)位。遞歸在這里負(fù)責(zé)維護(hù)多層嵌套循環(huán)的狀態(tài)你如果用普通的 for 循環(huán)寫全排列需要寫 N 層嵌套根本無(wú)法通用而遞歸讓嵌套深度變成了動(dòng)態(tài)的。這個(gè)案例告訴你一件事當(dāng)問題的復(fù)雜度體現(xiàn)在嵌套層數(shù)不確定時(shí)遞歸往往是最自然的表達(dá)方式。4. 快速排序的遞歸實(shí)現(xiàn)分治思想的集大成者4.1 快排的分區(qū)邏輯與遞歸主框架快排的核心思想是分治選一個(gè)基準(zhǔn)值把數(shù)組分成小于基準(zhǔn)和大于基準(zhǔn)兩部分然后遞歸地對(duì)兩部分排序。我推薦用 Lomuto 分區(qū)法代碼簡(jiǎn)潔容易理解def partition(arr, left, right): pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1這個(gè)分區(qū)的邏輯是遍歷[left, right)區(qū)間把所有小于 pivot 的元素?fù)Q到左邊i始終指向最后一個(gè)小于 pivot 的元素的位置最后把 pivot 放到i 1的位置上。此時(shí) pivot 已經(jīng)排到了正確的位置接下來遞歸去處理它左右兩側(cè)的子區(qū)間。遞歸主框架def quick_sort(arr, left, right): if left right: return pivot_idx partition(arr, left, right) quick_sort(arr, left, pivot_idx - 1) quick_sort(arr, pivot_idx 1, right)為什么遞歸終止條件是left right因?yàn)楫?dāng)區(qū)間里沒有元素left right或只有一個(gè)元素left right時(shí)它天然有序不需要繼續(xù)處理。整個(gè)思想可以用一句話概括每次讓一個(gè)元素落到最終位置然后縮小問題規(guī)模重復(fù)同樣的操作。4.2 快速排序的時(shí)間復(fù)雜度與遞歸深度快排的平均時(shí)間復(fù)雜度是 O(n log n)但這不是重點(diǎn)重點(diǎn)是遞歸深度帶來的棧壓力。理想情況下每次 partition 都能把數(shù)組分成兩半那么遞歸深度是 O(log n)大約 1000 個(gè)元素只需要 10 層左右的遞歸非常安全。最壞情況下比如數(shù)組已經(jīng)是有序的而 pivot 每次選到最大或最小元素分區(qū)嚴(yán)重不平衡一邊為空另一邊幾乎全量。這時(shí)遞歸深度是 O(n)也就是說對(duì) 100 萬(wàn)元素排序可能遞歸 100 萬(wàn)層直接棧溢出。所以純遞歸快排在工程上是有隱患的。很多教材不會(huì)告訴你這個(gè)細(xì)節(jié)但面試官往往就等在這里你能把快排寫成非遞歸嗎——他要的就是你用顯式棧替代系統(tǒng)調(diào)用棧。5. 快速排序非遞歸實(shí)現(xiàn)手寫棧模擬函數(shù)調(diào)用棧5.1 核心思路把待處理的子區(qū)間壓入顯式棧遞歸快排做的事情本質(zhì)上就是用系統(tǒng)調(diào)用棧記錄還需要排序的子區(qū)間。我們手動(dòng)做一個(gè)棧把子區(qū)間邊界[left, right]壓入棧中循環(huán)彈出、分區(qū)、再壓入新的子區(qū)間循環(huán)往復(fù)直到棧為空。為什么用棧而不是隊(duì)列其實(shí)都可以棧是 LIFO先處理后壓入的區(qū)間隊(duì)列是 FIFO按順序處理兩者最終都能完成排序只是處理順序不同、CPU 緩存局部性不同。但既然我們要模擬的是函數(shù)調(diào)用棧用棧更貼合原語(yǔ)義也更容易讓人理解。5.2 完整代碼與執(zhí)行過程逐行分析def quick_sort_iterative(arr): if len(arr) 1: return arr stack [(0, len(arr) - 1)] while stack: left, right stack.pop() if left right: continue pivot_idx partition(arr, left, right) # 壓入左子區(qū)間 if pivot_idx - 1 left: stack.append((left, pivot_idx - 1)) # 壓入右子區(qū)間 if pivot_idx 1 right: stack.append((pivot_idx 1, right)) return arr用一個(gè)例子走一遍。假設(shè)arr [5, 3, 8, 4, 2]。初始stack [(0, 4)]。第一次循環(huán)彈出(0, 4)調(diào)用partition(arr, 0, 4)pivot 選arr[4] 2分區(qū)結(jié)果是[2, 3, 8, 4, 5]返回pivot_idx 0。左邊區(qū)間(0, -1)無(wú)效不壓棧。右邊區(qū)間(1, 4)壓入棧。第二次循環(huán)彈出(1, 4)對(duì)[3, 8, 4, 5]分區(qū)pivot 選5結(jié)果變成[3, 4, 2, 5, 8]的局部調(diào)整整體數(shù)組為[2, 3, 4, 5, 8]返回pivot_idx 3。左邊區(qū)間(1, 2)壓入棧右邊區(qū)間(4, 4)無(wú)效不壓棧。第三次循環(huán)彈出(1, 2)對(duì)[3, 4]分區(qū)返回pivot_idx 2兩邊區(qū)間都無(wú)效不壓棧。?？张判蛲瓿?。這個(gè)過程的關(guān)鍵點(diǎn)在于壓棧前的兩個(gè)if判斷只有當(dāng)子區(qū)間長(zhǎng)度大于 1 時(shí)才壓棧。這個(gè)判斷直接決定了循環(huán)能不能終止。你如果忽略了它就會(huì)把一個(gè)空區(qū)間無(wú)限壓棧彈出死循環(huán)跑不完。5.3 非遞歸快排的血淚經(jīng)驗(yàn)第一棧里存的是元組(left, right)千萬(wàn)別只存數(shù)組下標(biāo)總數(shù)。我見過有人圖省事只存數(shù)組長(zhǎng)度結(jié)果搞不懂到底該處理哪個(gè)區(qū)間代碼越改越亂。邊界這種東西一個(gè)元組清清楚楚。第二partition傳入的left、right要和上次遞歸快排完全一致。很多人寫遞歸的時(shí)候邊界是閉區(qū)間[left, right]改成非遞歸之后還是閉區(qū)間那就必須保證壓入的也是閉區(qū)間端點(diǎn)?；煊冒腴_半閉區(qū)間是 bug 重災(zāi)區(qū)我建議你在心里把區(qū)間定義為包含兩端的閉區(qū)間整套代碼統(tǒng)一。第三相比遞歸版本非遞歸快排的運(yùn)行速度不一定更快。它只是把系統(tǒng)棧換成了堆上的數(shù)組擺脫了棧深度限制但多了一道手動(dòng)管理數(shù)據(jù)結(jié)構(gòu)的工作。衡量它的價(jià)值在于穩(wěn)定性和可控性而不是性能上的絕對(duì)優(yōu)勢(shì)。6. 遞歸轉(zhuǎn)非遞歸的通用方法論6.1 三種常見改寫套路前面講快排非遞歸只是方法論的一個(gè)應(yīng)用實(shí)例現(xiàn)在把通用套路總結(jié)出來你會(huì)發(fā)現(xiàn)遞歸轉(zhuǎn)非遞歸其實(shí)有章可循。套路一尾遞歸直接改循環(huán)。尾遞歸指遞歸調(diào)用是函數(shù)的最后一個(gè)操作函數(shù)的返回值直接就是遞歸調(diào)用的返回值不需要再參與后續(xù)計(jì)算。比如def sum_to(n, acc0): if n 0: return acc return sum_to(n - 1, acc n)這種寫法本質(zhì)上就是循環(huán)直接改成def sum_to_iter(n): acc 0 while n 0: acc n n - 1 return acc套路二普通遞歸用顯式棧模擬?？炫啪褪沁@個(gè)套路的典型。核心工作是明確遞歸狀態(tài)是什么?？炫胚f歸狀態(tài)就是子區(qū)間邊界所以棧里存邊界。全排列遞歸狀態(tài)更復(fù)雜一點(diǎn)可能需要存當(dāng)前路徑所以棧里存路徑快照。抽象地說你只需要把遞歸函數(shù)的每個(gè)參數(shù)打包成元組壓入棧中循環(huán)出棧處理即可。套路三自底向上替代遞歸。很多遞歸問題本質(zhì)上是從大問題往下拆但如果你能明確知道最小子問題的答案就可以反過來從底部往上推。斐波那契的循環(huán)版本就是這類。這個(gè)思路和動(dòng)態(tài)規(guī)劃的重疊子問題一脈相承。6.2 什么場(chǎng)景值得改什么場(chǎng)景不值得改我的判斷標(biāo)準(zhǔn)很簡(jiǎn)單遞歸深度可能超過幾千、上萬(wàn)的必須改。遞歸深度只有幾十、幾百的比如目錄樹遍歷保留遞歸完全沒問題代碼還清晰。遞歸邏輯極其復(fù)雜比如解析嵌套 JSON、樹形結(jié)構(gòu)遍歷強(qiáng)行改非遞歸只會(huì)讓代碼失去可讀性如果不是棧溢出的硬約束我不建議改。面試被問到非遞歸寫法時(shí)既要寫得出也要能說出什么情況下選非遞歸的判斷標(biāo)準(zhǔn)這才是加分項(xiàng)。7. 遞歸調(diào)試三板斧打印、縮進(jìn)、邊界檢查7.1 用縮進(jìn)打印遞歸調(diào)用軌跡調(diào)試遞歸和調(diào)試普通循環(huán)完全不同。普通代碼的 bug 靠斷點(diǎn)一步步看能定位遞歸的 bug 往往藏在整個(gè)調(diào)用鏈里單步看容易看丟。我最常用的方法是在函數(shù)入口打印參數(shù)退出時(shí)打印返回值并用縮進(jìn)代表遞歸深度。def factorial_debug(n, depth0): indent * depth print(f{indent}enter factorial({n})) if n 1: print(f{indent}return 1 (base case)) return 1 result n * factorial_debug(n - 1, depth 1) print(f{indent}return {result}) return result factorial_debug(4)運(yùn)行結(jié)果enter factorial(4) enter factorial(3) enter factorial(2) enter factorial(1) return 1 (base case) return 2 return 6 return 24看到這個(gè)輸出你馬上能定位幾件事有沒有進(jìn)入終止條件、返回值是否按預(yù)期逐層傳遞、有沒有出現(xiàn)該返回卻一直往下調(diào)用的死循環(huán)。7.2 幾個(gè)高頻遞歸 bug 與排查思路我整理了這幾類每一類都在實(shí)際代碼評(píng)審中見過終止條件漏寫或?qū)戝e(cuò)位置比如快排里面用if left right而不是if left right單元素區(qū)間還在遞歸活活把棧撐爆。遞歸參數(shù)沒有向終止條件收斂比如fib(n - 1) fib(n - 2)中某個(gè)分支傳了n本身永遠(yuǎn)不減小。返回值被吞掉遞歸函數(shù)里只調(diào)用但不return導(dǎo)致上一層拿到None。這種 bug 特別隱蔽因?yàn)椴槐赖Y(jié)果全錯(cuò)。共享可變對(duì)象污染全排列里path[:]漏掉了[:]直接在 result 里存同一個(gè)列表引用最后所有結(jié)果都一樣。這類問題本質(zhì)上不是遞歸邏輯錯(cuò)而是 Python 可變對(duì)象的引用問題但遞歸場(chǎng)景特別容易犯。排查遞歸 bug 的時(shí)候我先問自己三個(gè)問題問題規(guī)模在縮小嗎終止條件是否覆蓋了所有最小情況每一層遞歸的返回值鏈路是否完整這三個(gè)問題能過濾掉絕大多數(shù)問題。最后再分享一個(gè)我個(gè)人的習(xí)慣寫遞歸前永遠(yuǎn)先在小規(guī)模輸入上手動(dòng)模擬一遍。模擬的時(shí)候只算前兩層后面靠規(guī)律推導(dǎo)而不是硬算到底。那些把遞歸想得太玄乎的人往往是因?yàn)閺囊婚_始就沒有親手跑過一個(gè)完整的調(diào)用過程。遞歸真的不是魔法它就是一只看不見的手在幫你壓棧彈棧而你一旦把這只看不見的手畫出來遞歸和非遞歸之間的那條鴻溝自然就消失了。