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