1. 遞歸到底是個什么東西很多人在學C語言的時候?qū)W到函數(shù)這塊就卡住了尤其是遞歸。數(shù)組、指針、結(jié)構(gòu)體好歹能看到實實在在的數(shù)據(jù)在內(nèi)存里怎么擺但遞歸這東西代碼看起來就那么幾行執(zhí)行起來卻像變魔術(shù)一樣讓人摸不著頭腦。先給一個粗暴但準確的定義遞歸就是函數(shù)自己調(diào)用自己。不是函數(shù)的拷貝是同一個函數(shù)在執(zhí)行的過程中又調(diào)用了自己。這句話看起來簡單但很多初學者第一個疑惑就是它調(diào)用自己那不就無限循環(huán)了嗎程序不得爆掉問得好這正是遞歸的核心問題。答案在于遞歸必須滿足兩個關(guān)鍵條件遞歸出口和遞推公式。沒有出口的遞歸就是死循環(huán)遲早把?？臻g耗盡導致程序崩潰沒有遞推關(guān)系的遞歸就是原地打轉(zhuǎn)毫無意義。舉個例子計算n的階乘int factorial(int n) { if (n 1) { return 1; // 遞歸出口 } return n * factorial(n - 1); // 遞推公式 }你執(zhí)行factorial(5)的時候函數(shù)并不會立刻算出結(jié)果。它會先變成5 * factorial(4)然后變成5 * 4 * factorial(3)層層遞進一直到5 * 4 * 3 * 2 * factorial(1)碰到出口條件n 1返回1然后再一層層歸回來5*4*3*2*1。整個過程可以想象成查字典你要查久字發(fā)現(xiàn)解釋里有個遙字不認識于是去查遙結(jié)果遙的解釋里又有遠字不認識再去查遠……直到查到一個所有字都認識的字條才能一層層倒回去最終弄明白久是什么意思。這個從入口一路問到出口再從出口一路帶回答案的過程就是遞歸最核心的邏輯。那什么樣的問題適合用遞歸理論上只要一個問題能被拆成規(guī)模更小但結(jié)構(gòu)相同的子問題就適合遞歸。最典型的就在兩個經(jīng)典問題上漢諾塔和青蛙跳臺階。這篇文章就把這兩個問題從頭到尾拆開揉碎講清楚順帶把遞歸的底層機制、性能陷阱、調(diào)試技巧一網(wǎng)打盡。2. 遞歸背后的執(zhí)行機制在動手寫代碼之前必須先把遞歸的底層執(zhí)行機制搞明白否則你寫出來的遞歸就是碰運氣對了不知道為什么對錯了也不知道怎么改。2.1 棧幀函數(shù)調(diào)用的真相C語言里每次函數(shù)調(diào)用系統(tǒng)都會在內(nèi)存的棧區(qū)stack分配一塊空間叫棧幀stack frame。這個棧幀里保存了三個關(guān)鍵信息函數(shù)的局部變量、參數(shù)值以及返回地址——也就是調(diào)用完這個函數(shù)后該回到哪里繼續(xù)執(zhí)行。每次調(diào)用新函數(shù)就壓入一個新棧幀每次函數(shù)返回就彈出棧頂幀。這和我們平時摞盤子一模一樣后放上去的先拿下來這叫后進先出。重點是遞歸調(diào)用時每次調(diào)用同一個函數(shù)會創(chuàng)建不同的棧幀。你以為它們在同一個函數(shù)里其實每一層的局部變量都獨立存在互不干擾。比如上面階乘的例子遞歸第5層的那個n和第4層的n雖然名字都叫n但它們住的是不同的房間。這就能解釋一個很多新手都會犯的錯在遞歸函數(shù)里用了全局變量或靜態(tài)變量來保存中間結(jié)果。這些變量是全函數(shù)共享的不是每層獨立的。你這一層的修改下一層看得見下一層改了上一層也會受影響最后結(jié)果全亂套。所以寫遞歸優(yōu)先用參數(shù)和返回值傳遞數(shù)據(jù)別依賴全局狀態(tài)這是第一條鐵律。2.2 遞歸的遞與歸遞歸的執(zhí)行過程可以拆成兩個階段遞——一層層調(diào)用下去直到碰到出口歸——出口返回結(jié)果結(jié)果一層層倒著傳回來。還是看階乘factorial(5)的完整過程遞factorial(5) → 5 * factorial(4) 遞factorial(4) → 4 * factorial(3) 遞factorial(3) → 3 * factorial(2) 遞factorial(2) → 2 * factorial(1) 遞factorial(1) → 1 // 到達出口 歸factorial(1) 返回 1 歸factorial(2) 返回 2 * 1 2 歸factorial(3) 返回 3 * 2 6 歸factorial(4) 返回 4 * 6 24 歸factorial(5) 返回 5 * 24 120看到?jīng)]有遞的時候從大到小歸的時候從小到大后調(diào)用的先返回。一句話先深入再回溯這就是遞歸的本質(zhì)節(jié)奏。很多同學看完遞就暈了其實真正計算發(fā)生在歸的階段。你想factorial(5)里的那個* factorial(4)要等factorial(4)算出結(jié)果才能執(zhí)行乘法運算所以真正干活的時機是歸的過程。遞歸的代碼寫在調(diào)用自己之前是遞的時候干活寫在自己之后是歸的時候干活。這個理解對后面的漢諾塔特別關(guān)鍵——它的輸出語句放在兩次遞歸調(diào)用的中間執(zhí)行順序非常反直覺。2.3 遞歸深度和棧溢出棧區(qū)空間是有限的不同平臺不一樣常見默認在1MB~8MB。每次函數(shù)調(diào)用占用多少棧幀取決于局部變量大小幾十到幾百字節(jié)很正常。所以一個遞歸能深入多少層是有上限的。如果遞歸深度太大棧幀不斷壓入最終超出棧的容量就會觸發(fā)棧溢出stack overflow程序直接崩潰。我在Linux上試過一個不帶額外局部變量的空遞歸函數(shù)深度大概到幾十萬層就會段錯誤。實操里我一般給你一個經(jīng)驗紅線遞歸深度在1萬層以內(nèi)比較安全超過就要考慮改寫成迭代或者深度優(yōu)先搜索配顯式棧。刷題網(wǎng)站上經(jīng)常有斐波那契那種記憶化遞歸突然爆棧的問題十有八九就是這個深度問題不是你的邏輯錯了。3. 漢諾塔問題全拆解漢諾塔Hanoi Tower應(yīng)該是最能體現(xiàn)遞歸魅力的題目了沒有之一。初見時覺得巨難無比搞懂之后會覺得遞歸真他媽優(yōu)雅。3.1 問題描述有3根柱子分別叫A起始柱、B輔助柱、C目標柱。A柱上從下往上按大小順序摞著n個圓盤。要求把所有圓盤從A移到C規(guī)則有兩條每次只能移動一個圓盤任何時候大盤不能壓在小盤上面問n個圓盤時最少需要移動多少次每一步怎么移3.2 從最小的規(guī)模開始找感覺面對這種問題不要一上來就想著n個盤子。我們先從最簡單的開始推。n1一個盤子直接從A移到C完成。共1步。n2兩個盤子小盤1號在大盤2號上面。1號盤A → B先把小的挪開2號盤A → C大的直接去目標位1號盤B → C小的再挪到大的上面共3步。n3三個盤子的時候情況就開始復雜了但核心思路是先把上面2個盤子從A移到B借助C——這一步怎么移就是上面n2的過程只是目標柱從C換成了B再把最大的3號盤從A移到C最后把B上的2個盤子移到C借助A——這又是一次n2的移動你發(fā)現(xiàn)規(guī)律了嗎不管多少個盤子移動n個盤子的問題總是可以拆成三步把上面的 n-1 個盤子從 A 移到 B借助 C把最底下的第 n 個盤子從 A 移到 C把 B 上的 n-1 個盤子從 C 移到目標 C借助 A而把n-1個盤子從某根柱移到另一根柱又是一個規(guī)模更小、規(guī)則完全相同的漢諾塔問題。這不就是遞歸嗎3.3 代碼實現(xiàn)#include stdio.h void hanoi(int n, char from, char tmp, char to) { if (n 1) { // 只有一個盤子直接移動 printf(第1個盤: %c - %c\n, from, to); return; } // 第一步把上面n-1個盤子從from移到tmp借助to hanoi(n - 1, from, to, tmp); // 第二步把第n個盤子從from移到to printf(第%d個盤: %c - %c\n, n, from, to); // 第三步把tmp上的n-1個盤子從tmp移到to借助from hanoi(n - 1, tmp, from, to); } int main() { int n 3; printf(移動 %d 個盤子的步驟:\n, n); hanoi(n, A, B, C); return 0; }運行結(jié)果移動 3 個盤子的步驟: 第1個盤: A - C 第2個盤: A - B 第1個盤: C - B 第3個盤: A - C 第1個盤: B - A 第2個盤: B - C 第1個盤: A - C正好7步。你可以拿紙和筆拿三個硬幣模擬一下每一步都對得上。這個函數(shù)的參數(shù)設(shè)計有一個細節(jié)需要注意from、tmp、to三個參數(shù)表示的是角色不是固定某根柱子。同一根柱子在這一層調(diào)用里可能是from在下一層調(diào)用里就變成了tmp。很多同學看遞歸看暈就是沒轉(zhuǎn)過這個彎來——函數(shù)參數(shù)的含義是現(xiàn)場的、臨時的A/B/C是具體的角色是會變化的。3.4 為什么這個代碼是對的很多人第一次看到這個代碼最大的困惑是不就三行調(diào)用嗎憑什么它能算出正確的移動步驟我們一層層看。假設(shè)hanoi(3, A, B, C)第一步調(diào)用hanoi(2, A, C, B)意思是我要把2個盤子從A移到B用C做輔助。這本身就是一個子問題。它內(nèi)部先調(diào)用hanoi(1, A, B, C)輸出A→C第1號盤先挪走輸出2號盤A→B再調(diào)用hanoi(1, C, A, B)輸出C→B回到外層輸出3號盤A→C再調(diào)用hanoi(2, B, A, C)把2個盤子從B移到C用A做輔助。內(nèi)部先輸出B→A輸出2號盤B→C輸出A→C關(guān)鍵在于每一層都只關(guān)心怎么把當前這堆盤子當成一個整體來挪至于挪的過程中內(nèi)部怎么折騰完全交給下一層遞歸處理。你不需要在腦子里把每一層每一步都展開你只需要相信只要子問題能被正確解決那組合起來整個問題就解決了。這就是遞歸里的相信過程。這種大事化小、小事化了的思路在算法上有個正式名字叫分治法把一個大問題分解成若干個獨立的、規(guī)模更小的同類子問題分別求解再合并結(jié)果。3.5 最少移動次數(shù)推導漢諾塔問題還有一個經(jīng)典變體問n個盤子最少需要移多少次。設(shè)f(n)表示n個盤子的最少移動次數(shù)根據(jù)前面拆解的三步移走上面n-1個盤子f(n-1)次移最下面的大盤1次再把n-1個盤子移回來f(n-1)次所以遞推關(guān)系是f(n) 2 * f(n-1) 1 f(1) 1展開一下f(1) 1 f(2) 2*1 1 3 f(3) 2*3 1 7 f(4) 2*7 1 15看出規(guī)律沒有f(n) 2^n - 1。64個盤子的傳說需要的次數(shù)是2^64 - 1按一秒移一次得5849億年比宇宙年齡還長這就是指數(shù)爆炸的威力。這個推導過程也完美體現(xiàn)了遞歸思維的另一層用法用遞推公式描述問題規(guī)模的增長規(guī)律。很多時候你不需要真的去模擬每一步用一個遞推式就能分析出復雜度。3.6 漢諾塔的常見變體和坑變體1目標柱不同的漢諾塔。比如要求從A移到BC是輔助那么調(diào)用hanoi(n, A, C, B)就行邏輯不用改。變體2返回步數(shù)。不改打印功能加一個返回值int hanoi_count(int n, char from, char tmp, char to) { if (n 1) { printf(第1個盤: %c - %c\n, from, to); return 1; } int count 0; count hanoi_count(n - 1, from, to, tmp); printf(第%d個盤: %c - %c\n, n, from, to); count; count hanoi_count(n - 1, tmp, from, to); return count; }坑1打印語句的順序。漢諾塔的打印語句夾在兩個遞歸調(diào)用中間這意味著歸的時候先執(zhí)行完第一個遞歸打印當前層再執(zhí)行第二個遞歸。這個順序一旦寫反整個移動步驟就是錯的。正確邏輯必須是先把小的移到輔助柱再動大盤最后把小的移到目標柱。三大步的順序絕不能亂。坑2遞歸出口必須最先判。很多人喜歡把if (n1)寫到最后面或者不寫出口直接寫if (n0) return;也能跑但容易在傳0的時候出問題。我建議統(tǒng)一n1作為出口邏輯最直觀。4. 青蛙跳臺階問題精解如果說漢諾塔是遞歸的形那青蛙跳臺階就是遞歸的神——它背后藏著動態(tài)規(guī)劃和斐波那契數(shù)列是面試場上出現(xiàn)頻率極高的題目。4.1 問題描述一只青蛙一次可以跳上1級臺階也可以跳上2級臺階。請問它跳上n級臺階總共有多少種跳法注意這里問的是多少種跳法不是具體每一步怎么跳。這是個計數(shù)問題最怕的就是一上來就在腦子里枚舉所有路徑很快就會亂。正確姿勢是把問題遞推化。4.2 遞推思路推導假設(shè)f(n)表示跳上n級臺階的跳法數(shù)。先看最簡單的f(1)只有1級臺階只能跳1級1種跳法。f(2)可以11跳兩次也可以直接跳2級2種跳法?，F(xiàn)在跳到關(guān)鍵的n了。青蛙在第一跳只有兩種選擇跳1級或者跳2級。如果第一跳跳1級那剩余n-1級臺階的跳法就是f(n-1)種。如果第一跳跳2級那剩余n-2級臺階的跳法就是f(n-2)種。這兩種情況互斥且完備不可能同時發(fā)生也不會漏掉任何情況所以f(n) f(n-1) f(n-2) f(1) 1 f(2) 2看到這個遞推式熟悉斐波那契數(shù)列的同學應(yīng)該已經(jīng)反應(yīng)過來了這不就是斐波那契嗎標準的斐波那契是F(1)1, F(2)1, F(n)F(n-1)F(n-2)青蛙跳臺階只是把第二項從1改成了2。用表格列一下n123456f(n)1235813驗證一下n3跳法為 111、12、21正好3種。n41111、112、121、211、22正好5種。沒問題。4.3 樸素遞歸實現(xiàn)#include stdio.h int jump(int n) { if (n 1) { return 1; } if (n 2) { return 2; } return jump(n - 1) jump(n - 2); } int main() { for (int i 1; i 10; i) { printf(jump(%d) %d\n, i, jump(i)); } return 0; }這段代碼邏輯完全正確但你拿它跑jump(45)會發(fā)現(xiàn)越來越慢跑jump(50)可能就要等好久。問題出在哪4.4 遞歸的性能陷阱把jump(5)的調(diào)用關(guān)系畫出來jump(5) ├── jump(4) │ ├── jump(3) │ │ ├── jump(2) │ │ └── jump(1) │ └── jump(2) └── jump(3) ├── jump(2) └── jump(1)看到?jīng)]有jump(3)被算了2次jump(2)被算了3次。n越大重復計算的次數(shù)呈指數(shù)增長。jump(50)需要計算的次數(shù)大約是2^50級別這誰扛得住這就是遞歸最典型的性能坑當一個遞歸會把同一個子問題重復計算很多次的時候它的時間復雜度是指數(shù)級的。斐波那契的樸素遞歸時間復雜度是O(2^n)聽起來就嚇人。解決思路有兩條記憶化搜索把算過的結(jié)果存起來和改成迭代從底部往上算。這兩個方案下面各寫一段。4.5 優(yōu)化方案一記憶化遞歸思路很簡單第一次算出jump(3)之后把結(jié)果存在一個數(shù)組里后面再要jump(3)直接查表返回不重復遞歸。#include stdio.h #define MAX 100 long long memo[MAX] {0}; long long jump_memo(int n) { if (n 1) { return 1; } if (n 2) { return 2; } if (memo[n] ! 0) { return memo[n]; } memo[n] jump_memo(n - 1) jump_memo(n - 2); return memo[n]; } int main() { for (int i 1; i 50; i) { printf(jump(%d) %lld\n, i, jump_memo(i)); } return 0; }加了一個memo數(shù)組每個子問題只算一次時間復雜度直接從O(2^n)降到O(n)。我實測跑jump(50)瞬間出結(jié)果。注意我用了long long因為jump(50)的結(jié)果超過int的范圍了——這是另一個容易踩的坑算到后面數(shù)字漲得飛快int根本裝不下。4.6 優(yōu)化方案二迭代遞推既然有了遞推公式f(n) f(n-1) f(n-2)那就完全沒必要用遞歸。直接用兩個變量滾著算#include stdio.h long long jump_iter(int n) { if (n 1) { return 1; } if (n 2) { return 2; } long long a 1; // f(n-2) long long b 2; // f(n-1) long long c 0; for (int i 3; i n; i) { c a b; a b; b c; } return c; } int main() { for (int i 1; i 50; i) { printf(jump(%d) %lld\n, i, jump_iter(i)); } return 0; }迭代版本連遞歸調(diào)用都沒了更不會爆?？臻g是O(1)時間還是O(n)。如果你被問到青蛙跳臺階面試官大概率會追一句能不能不用遞歸實現(xiàn)你直接把這個版本甩出來印象分拉滿。4.7 問題變體一次能跳n級同一道題的經(jīng)典變體如果青蛙一次可以跳1級、2級、……甚至n級那跳到第n級有多少種跳法推理稍微繞一點。設(shè)f(n)為跳法數(shù)。第一跳可以跳k級1 k n跳完k級后剩下n-k級的跳法數(shù)是f(n-k)所以f(n) f(n-1) f(n-2) ... f(1) f(0)其中f(0)表示一次直接跳完看作1種。展開這個式子f(n-1) f(n-2) f(n-3) ... f(1) f(0)兩個式子相減得到f(n) 2 * f(n-1)結(jié)合f(1) 1所以f(n) 2^(n-1)。這個拓展版本的核心思想是遞推關(guān)系的歸納與消元如果你把前面的f(n)f(n-1)f(n-2)理解透了這個變形其實不難推導。面試遇到這種變體能現(xiàn)場推出2^(n-1)這個結(jié)論說明你的遞推思維已經(jīng)過關(guān)了。5. 遞歸實戰(zhàn)的進階技巧理論吃透了代碼也會寫了接下來聊聊真正寫工程代碼、刷題、做筆試時用得上的實戰(zhàn)技巧。5.1 什么時候用遞歸什么時候別用我的建議是遞歸用在問題天然有遞歸結(jié)構(gòu)的場景比如樹的遍歷、目錄遍歷、分治排序快速排序、歸并排序、動態(tài)規(guī)劃的記憶化搜索。這些問題的數(shù)據(jù)結(jié)構(gòu)樹、圖本身就是遞歸定義的用遞歸順手得不得了。反過來如果問題本質(zhì)是線性的能一眼看出循環(huán)能解決就別硬遞歸。比如求和、求最大值、逐行處理文件用循環(huán)簡單明了非要遞歸反而把簡單問題搞復雜還增加棧溢出風險。至于遞歸和迭代怎么選給個參考場景推薦方案原因樹/圖遍歷遞歸結(jié)構(gòu)天然遞歸代碼極簡分治算法遞歸分解合并邏輯清晰大深度搜索如數(shù)獨迭代顯式棧避免棧溢出線性計算求和/階乘迭代性能更好更安全遞推關(guān)系斐波那契迭代/記憶化避免重復計算5.2 寫遞歸的三個固定步驟我自己帶人的時候都會教他們一個固定套路按這個順序想遞歸就不會亂定義函數(shù)簽名明確這個函數(shù)輸入什么、輸出什么。比如jump(int n)輸入臺階數(shù)輸出跳法數(shù)。找遞推關(guān)系想清楚當前問題和子問題之間的聯(lián)系。這一步往往需要你手動推幾個小規(guī)模case找到規(guī)律。確定遞歸出口最小的規(guī)模直接返回。注意出口必須覆蓋所有可能走到最小規(guī)模的情況不缺不漏。三步走完再翻譯成代碼。絕大部分寫不出遞歸的人都是卡在第二步——連遞推關(guān)系都沒想明白就急著寫代碼全憑感覺瞎試當然寫不出來。5.3 遞歸調(diào)試打印大法很多初學者調(diào)試遞歸有個壞習慣一看到結(jié)果不對就開始在腦子里模擬整個遞歸過程恨不得把每一個棧幀推演一遍。這不是人類干的事。正確的做法是在關(guān)鍵位置加打印語句看每一層的參數(shù)進來是什么、返回值是什么int jump_dbg(int n, int depth) { for (int i 0; i depth; i) { printf( ); } printf([%d] enter, n%d\n, depth, n); if (n 1) { printf([%d] return 1\n, depth); return 1; } if (n 2) { printf([%d] return 2\n, depth); return 2; } int res jump_dbg(n - 1, depth 1) jump_dbg(n - 2, depth 1); printf([%d] return %d\n, depth, res); return res; }用depth參數(shù)控制縮進每一層的日志一眼就能對上。看到哪一層的返回值不對問題就出在哪一層的遞推關(guān)系或出口上。不要用眼睛追蹤遞歸要讓計算機幫你把過程打印出來這是區(qū)分新手和老手的一個重要習慣。5.4 常見錯誤清單日常寫遞歸集齊這六種錯誤就能召喚神龍了。我一個個說你們一個個記。錯誤1遞歸出口缺失或永遠到達不了。函數(shù)一直在遞歸調(diào)用沒有停下來的條件最后棧溢出。典型代碼int f(int n) { return f(n - 1); // 沒有出口 }錯誤2出口條件寫錯導致提前返回。比如n0和n1的出口返回值給搞混結(jié)果整個遞推全錯。多檢查邊界值。錯誤3遞推公式寫錯。比如漢諾塔寫成了hanoi(n-1, from, to, tmp)卻把參數(shù)順序傳錯或者青蛙跳臺階寫成f(n-1) f(n)——后者就永遠遞歸不完這種錯誤往往在參數(shù)多的時候特別隱蔽。錯誤4忽略了遞歸的返回值。有些人喜歡在遞歸調(diào)用外面包一層卻忘了把返回值返回給上層void hanoi(int n, char from, char tmp, char to) { if (n 1) { printf(...); return; } hanoi(n - 1, from, to, tmp); // 如果這個函數(shù)需要有返回值你卻沒接收信息就丟了 ... }這個在C語言里特別邪門因為編譯器往往只給warning不給error程序能編譯能運行但結(jié)果就是不對。錯誤5重復計算導致超時。就是你寫的樸素斐波那契n一大就卡死。已經(jīng)講過了上記憶化或者循環(huán)。錯誤6int溢出。遞歸算到后面數(shù)字很大int不夠用。之前那個青蛙跳臺階算到46就超int了。習慣性用long long必要時上unsigned long long或者大數(shù)庫。6. 從遞歸到工程思維的升華遞歸學到最后你會發(fā)現(xiàn)它不只是C語言的一個語法技巧而是一種思維方式。它逼著你把大問題拆成小問題小問題拆成更小的問題直到每個問題都能直接求解。這個過程就是工程里常說的分而治之。6.1 遞歸思想在算法里的延伸掌握了遞歸的基礎(chǔ)你去看后面這些算法會特別順暢歸并排序把數(shù)組對半分分別排序再合并。分治思想的教科書級應(yīng)用?？焖倥判蜻x一個基準把數(shù)組分成左右兩半遞歸排序。樹的遍歷二叉樹的前序/中序/后序遍歷代碼極其優(yōu)雅基本就是三行遞歸?；厮菟惴ò嘶屎?、數(shù)獨、全排列核心框架就是遞歸撤銷選擇。深度優(yōu)先搜索走迷宮、圖的連通性判斷一個DFS函數(shù)遞歸調(diào)用自己配上visited數(shù)組標記就能走遍整張圖。很多人學算法覺得難一個很重要的原因是遞歸思維沒建立起來。因為算法世界里到處都是遞歸結(jié)構(gòu)你不會遞歸看啥都像天書你會了很多東西就一通百通了。6.2 C語言遞歸性能的幾個優(yōu)化細節(jié)如果你在寫性能敏感的程序比如嵌入式、游戲服務(wù)器遞歸有這幾個錦上添花的點尾遞歸優(yōu)化。如果遞歸調(diào)用是函數(shù)的最后一個操作并且結(jié)果直接返回這種叫尾遞歸?，F(xiàn)代編譯器一般能把它優(yōu)化成循環(huán)避免棧深度增長。C語言標準本身不強制要求尾調(diào)用優(yōu)化但GCC在優(yōu)化級別-O2以上通常能做。想確認可以反匯編看生成的代碼里還有沒有call指令。// 尾遞歸版本的寫法 int factorial_tail(int n, int acc) { if (n 1) { return acc; } return factorial_tail(n - 1, acc * n); }內(nèi)聯(lián)函數(shù)。在C99或C11里用inline關(guān)鍵字提示編譯器把短小的函數(shù)體直接嵌入到調(diào)用處省去函數(shù)調(diào)用開銷。但遞歸函數(shù)通常不建議內(nèi)聯(lián)因為無法完全展開而且代碼體積會膨脹。小遞歸函數(shù)可以試試大遞歸別碰。善用靜態(tài)/動態(tài)規(guī)劃。遞歸只是手段不是目的。一個問題能遞推就不要純遞歸能用迭代就用迭代。最經(jīng)典的反例就是斐波那契純遞歸的時間復雜度是O(2^n)迭代是O(n)差了天和地。遞歸的價值在于清晰如果清晰和高效發(fā)生沖突工程里優(yōu)先保證清晰但如果你發(fā)現(xiàn)復雜度已經(jīng)不是常數(shù)級別的差距那必須考慮優(yōu)化方案來做折中。6.3 從面試角度聊聊這兩道題面試官問漢諾塔、青蛙跳臺階其實想考察的是三件事第一你能不能建模。給你一個具體問題你能不能抽象出遞推關(guān)系。很多人卡在這一步是因為腦子里沒有假設(shè)子問題已解決這個概念。你得敢說假設(shè)我已經(jīng)知道怎么移n-1個盤子了然后在此基礎(chǔ)上推導n個盤子。第二你知不知道邊界條件。也就是遞歸出口。出口寫不對或者寫不全代碼就跑不對。第三你了不了解性能邊界。青蛙跳臺階問完之后面試官多半會追問你的遞歸有什么問題怎么優(yōu)化。能主動說出重復計算、記憶化、迭代三個優(yōu)化方向基本就是加分項。我見過太多人去面試青蛙跳臺階的遞歸代碼寫出來了結(jié)果問一句這個時間復雜度是多少直接卡殼再問怎么優(yōu)化就抓瞎。所以這里再強調(diào)一遍題目能AC只是及格能分析復雜度、能優(yōu)化、能變體擴展才是面試官真正想看的。6.4 我的一些個人體會寫遞歸寫了這么多年最大的感悟是遞歸的核心不是代碼而是信任。你要相信只要遞推關(guān)系和出口都是對的計算機一定能給你跑出正確結(jié)果。初學者最怕的是不信任遞歸的自我修復能力總想手動干預(yù)中間過程結(jié)果越改越亂。第二個感悟是遞歸這東西光看是真的看不懂的必須動手推。我教過很多學生最快的入門方式就是拿3個、4個硬幣照著漢諾塔的打印結(jié)果一行一行模擬親手把每步移動擺出來。擺過3遍你就再也不會忘記漢諾塔為什么是那樣寫的了。最后如果你現(xiàn)在正在為C語言里某個遞歸題目抓狂我給你一個可執(zhí)行的建議別盯著屏幕發(fā)呆拿支筆把調(diào)用樹一層一層展開在紙上把每一層的參數(shù)和返回值標出來。展開到第三層你基本就能看清整個邏輯了。這個方法土但百分之百管用。