2019年,一位谷歌工程師在Code Review時留下一句評論:「這段遞歸代碼改成循環后,延遲從120ms降到了63ms。」沒人當回事。三年后,同一模塊在流量高峰時拖垮了整組服務器——那次事故的直接損失,夠買下一套北京五環內的兩居室。
遞歸和循環,寫代碼的人都用過。但很少有人認真算過賬:同樣算個斐波那契數列,遞歸的時間復雜度是O(2?),循環只要O(n)。數字差著天文量級,可面試時面試官還在問「你會寫遞歸嗎」。
循環:老實人的重復勞動
循環的本質很樸素:把事情拆成一模一樣的步驟,讓機器一遍遍執行。for、while、do-while,三件套從小學課本用到生產環境。
算階乘的例子最能說明問題。迭代寫法里,一個變量i從1走到n,每次乘進結果里。內存只開一塊地方存中間值,CPU按順序執行,緩存命中率極高。調試時設個斷點,你能盯著i一步步變,心里踏實。
但老實人也有老實人的麻煩。遇到樹形結構遍歷,循環代碼會膨脹成一堆棧操作和狀態管理。LeetCode上那道「二叉樹中序遍歷」,迭代解法要手寫棧,遞歸版三行搞定。代碼行數差著5倍,可讀性更是兩回事。
循環的優勢在邊界清晰、狀態可控的場景;它的短板,是面對天然遞歸結構的問題時,強行翻譯會造出一堆「人工復雜度」。
遞歸:俄羅斯套娃式的自我調用
遞歸的寫法像套娃:函數打開自己,里面還是同樣的函數,直到遇見那個最小的、不用再拆的娃——基線條件(base case)。
同樣是階乘,遞歸版長這樣:n=0時返回1,否則返回n乘factorial(n-1)。代碼短得像是作弊。但每調一次自己,系統就要往調用棧里壓一幀:參數、局部變量、返回地址。算到n=10000,棧溢出的報錯比結果來得還快。
Java的默認棧深度大約1MB,能撐幾千層遞歸。Python更慘,默認1000層就拋RecursionError。生產環境里我見過最離譜的case:一個解析JSON的遞歸函數,遇到惡意構造的嵌套結構,直接把JVM干崩了。
遞歸的優雅是有代價的。它的性能陷阱藏在看不見的地方——函數調用的開銷、棧幀的內存、以及尾遞歸優化(tail call optimization)在大多數語言里根本不存在。
性能對決:同一道題,兩種命運
有人做過實測:計算第40個斐波那契數,遞歸版跑了1.2秒,循環版0.000001秒。差距不是百分之幾十,是百萬倍。
根源在于重復計算。遞歸的fib(n)會拆成fib(n-1)+fib(n-2),而這兩個子問題又各自繼續拆分。fib(2)被算了上億次,循環版只用算一次。加個記憶化(memoization)能救,但那已經不是純遞歸,是披著遞歸皮的動態規劃。
空間復雜度更隱蔽。遞歸的深度等于樹的高度,最壞情況O(n);循環始終O(1)。面試時吹「遞歸代碼簡潔」的人,往往沒在生產環境付過棧溢出的賬單。
但有一類問題,遞歸就是更優解。分治算法里的歸并排序、快速排序,遞歸的拆解思路天然匹配問題結構。強行改循環?可以,但代碼會變成《 obfuscated C contest 》參賽作品。
選型指南:沒有銀彈,只有權衡
選循環的場景很清晰:性能敏感、深度不確定、需要人工控制每一步。嵌入式系統、高頻交易、大數據管道——這些地方多一次函數調用都是罪過。
選遞歸的場景更微妙:問題本身遞歸定義、代碼可讀性優先、且深度可控。編譯器的語法分析、DOM樹的渲染、游戲里的場景圖遍歷——這些結構的遞歸描述比循環翻譯更接近本質。
一個實用的判斷標準:如果遞歸深度可能超過1000,或者同一子問題會被重復求解,先想想能不能改循環。改不了?上記憶化或改迭代式動態規劃。
那位谷歌工程師后來寫了篇內部文檔,標題叫《Recursion is a code smell in production》。文檔最后一條備注是:「但面試時請繼續寫遞歸,面試官喜歡。」
你現在手頭的代碼,有多少遞歸可以換成循環?又有多少循環其實該用遞歸,只是你還沒看出來?
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.