谷歌工程師踩坑3年才發現：遞歸比循環慢47%的真相

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》。文檔最后一條備注是：「但面試時請繼續寫遞歸，面試官喜歡。」

你現在手頭的代碼，有多少遞歸可以換成循環？又有多少循環其實該用遞歸，只是你還沒看出來？