作者 | Cooper Song
責編 | Elle
出品 | 程序人生（ID：coder_life）
我猜，大多數程序員第一次接觸函數的遞歸調用都是在算斐波那契數列某項值的時候，這是函數遞歸調用最常見的應用之一。規定第一項和第二項為1，后面的項，每一項都是其前面兩項的和。
用公式表示就是f(n)=f(n-2)+f(n-1)。
而進一步轉化，就是f(n)=[f(n-2-2)+f(n-2-1)]+[f(n-1-2)+f(n-1-1)]。
很明顯，這是一個遞歸的過程。
遞歸的優點是算法簡單、容易理解，代碼行數少。
但遞歸也有缺點，咱們將上面的f(n)再化簡一下就變成了f(n)=[f(n-4)+f(n-3)]+[f(n-3)+f(n-2)]，可以看出，f(n-3)被計算了兩次，而f(n-4)+f(n-3)就是再計算f(n-2)，又與最后一項f(n-2)是一樣的，f(n-2)也被重復計算了。因此，遞歸的一大缺點就是存在大量的重復計算，運行起來浪費時間也浪費空間。
遞歸的另一個缺點是遞歸的層數不能太多（不能遞歸太深）。那遞歸得太深了會怎樣呢？答案是會爆棧。那么什么是爆棧呢？又是怎樣引發爆棧的呢？下面就要從最底層的角度講一講函數調用及函數遞歸調用的原理，相信讀完了就會找到答案。
這就要先從程序的鏈接和裝入說起了。
程序的鏈接（Link）
一個程序是由多個模塊構成的，以C語言為例，有頭文件<stdio.h>，只有引用了這個頭文件你才能使用scanf和printf；還有頭文件<string.h>，只有引用了這個頭文件你才能直接調用strlen函數得到字符串的大小。所謂程序的鏈接，就是將整個程序的所有目標模塊（比如程序員自己寫的頭文件和函數）以及其他所需要的庫函數裝配成一個完整的裝入模塊。
原來每個模塊都有每個模塊的邏輯地址，經過鏈接后，形成了統一的從0開始的邏輯地址，如下圖所示。
如何理解模塊？看上圖大概就有了概念，一個函數就是一個模塊。
程序的裝入（Load）
學過計算機組成原理的同學都知道，在計算機中有個部件叫程序計數器（Program Counter，簡稱PC），它存放的是程序要執行的下一條指令的地址，CPU要到內存當中去取指令，取到CPU中進行譯碼分析然后執行。
程序原本存儲在磁盤上，因此只經過鏈接還不能運行，還需要裝入主存（內存），CPU通過PC提供的線索到內存中去取指令，如此循環往復，程序才得以運行下去。雖然程序的第一條指令的邏輯地址是0，但它裝入內存時在內存中的地址可不是0，因為內存中的低地址是留給系統使用的，也就是系統區，比系統區的地址高的空間才是留給用戶使用的，也就是用戶區。雖然裝入內存后其地址不再是從0開始，但其相對地址是不變的，將上面鏈接好的裝入模塊裝入內存，內存空間示意圖如下。
函數的調用
所謂函數的調用，就是程序原本在主模塊中順序執行，遇到調用指令暫時到別的模塊執行，在別的模塊執行完后再返回主模塊的下一條指令繼續執行，如下圖所示。
為什么可以執行著執行著就跳到別的模塊執行了？又為什么在別的模塊執行完了又回到原來的模塊執行了呢？之所以能跳到別的模塊執行，是因為函數調用指令就指明了目標模塊的首地址，將目標模塊的首地址傳送給了程序計數器PC，就中斷了程序的順序執行，然后進入目標模塊執行。之所以執行完子模塊還能回到主模塊中執行，是因為內存中有一個專門實現函數調用的棧區，在執行調用指令的時候，就將主模塊調用指令之后的指令的地址入了棧，當子模塊執行到返回指令的時候，再出棧，將棧頂元素（也就是主模塊中要執行的下一條指令的地址）傳給PC，程序的執行就又回到了主模塊。
假設模塊A中的指令是：
add ax,bx ;本條指令的地址為10000
call B ;調用模塊B本條指令的地址為10001
mov dx,ax ;本條指令的地址為10002
假設模塊B中的指令是：
sub cx,dx ;本條指令的地址為15000
mov bx,cx ;本條指令的地址為15001
ret ;本條指令的地址為15002
模塊A為主模塊，模塊B為目標模塊，在執行call B指令的時候，函數調用棧區示意圖如下（左邊為調用前，右邊為調用后），SP為棧頂指針。
執行完call B，就開始在模塊B中執行，一直執行到ret返回指令，此時函數調用棧區示意圖如下（左邊為返回后，右邊為返回前）。
執行完ret返回指令，將棧頂元素出棧送給程序計數器PC以供CPU繼續執行主模塊A中的剩余指令。
實際上，函數調用時入棧保護的不僅僅有主模塊中調用指令之后的指令的地址，還有一些變量或者說數據，每個函數都有每個函數的局部變量，在主函數中調用子函數，主函數中的局部變量必須入棧保護，否則就會丟失。比如下面這個例子：
int add(int x,int y)
{
int a=x+1;
int b=y+1;
int c=a+b;
return c;
}
int main
{
int a=1,b=2;
int c=add(a,b);
printf(“%d+%d=%d ”,a,b,c);
return 0;
}
主函數和add函數里都有變量a和b，執行完add函數再返回到主函數中a的值必須還為1，b的值必須還為2，因此可以在調用add函數前先將主函數的所有變量（a和b）入棧保護，待執行完返回主函數時再出棧送給變量a和變量b。
遞歸函數的調用
遞歸函數的調用本質上也是函數的調用，只不過是自己在調用自己罷了。
以求斐波那契數列的項為例：
int fibonacci(int n)
{
if(n==1||n==2) //假設本條指令的地址為10000
return 1; //假設本條指令的地址為10001
int a=fibonacci(n-2); //假設本條指令的地址為10002
int b=fibonacci(n-1); //假設本條指令的地址為10003
int c=a+b; //假設本條指令的地址為10004
return c; //假設本條指令的地址為10005
}
如果進入函數的n是1或者是2，那么就直接返回1；
否則，就繼續遞歸下去。
假設主函數調用斐波那契函數的指令的地址為15000，其下一條指令的地址為15001。
假設我們要求斐波那契數列的第5項，公式為
f(5)=f(3)+f(4)
=[f(1)+f(2)]+[f(2)+f(3)]
=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]
函數調用棧的示意圖如下。
第一步，從主函數中進入斐波那契函數，傳入的n為5。
第二步，斐波那契函數中執行到int a=fibonacci(n-2)，將下一條指令的地址壓入棧，也就是將10003入棧，此時的n=5，將n=5壓入數據棧，傳入的n=3。
第三步，斐波那契函數中執行到int a=fibonacci(n-2)，將下一條指令的地址壓入棧，也就是將10003入棧，此時的n=3，將n=3壓入數據棧，傳入的n=1。
第四步，此時n=1，可以直接返回1給上層的斐波那契函數的a，返回的同時出棧10003給程序計數器PC，出棧n=3給上一層斐波那契函數的n，回到上層的斐波那契函數。
第五步，執行程序計數器PC指向的指令（內存地址為10003的指令），也就是執行int b=fibonacci(n-1)，是一個函數調用，將下一條指令的地址壓入棧，也就是將10004入棧，此時n=3，將n=3壓入數據棧，此時a=1，將a=1壓入數據棧，傳入的n=2。
第六步，此時n=2，可以直接返回1給上層斐波那契函數的b，返回的同時出棧10004給程序計數器PC，出棧n=3給上一層斐波那契函數的n，出棧a=1給上一層斐波那契函數的a，回到了上層的斐波那契函數。
第七步，執行程序計數器PC指向的指令（內存地址為10004的指令），也就是執行int c=a+b，然后順序執行一直到返回，返回2給上一層斐波那契函數的a，返回的同時出棧10003給程序計數器PC，出棧n=5給上一層的斐波那契函數的n，回到上層的斐波那契函數。
f(5)=f(3)+f(4)
=[f(1)+f(2)]+[f(2)+f(3)]
=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]
此時紅色部分已通過遞歸計算完成。
第八步，執行程序計數器PC指向的指令（內存地址為10003的指令），也就是執行int b=fibonacci(n-1)，是一個函數調用，將下一條指令的地址壓入棧，也就是將10004入棧，此時n=5，將n=5壓入數據棧，此時a=2，將a=2壓入數據棧，傳入的n=4。
第九步，斐波那契函數中執行到int a=fibonacci(n-2)，將下一條指令的地址壓入棧，也就是將10003入棧，此時的n=4，將n=4壓入數據棧，傳入的n=2。
第十步，此時n=2，可以直接返回1給上層的斐波那契函數的a，返回的同時出棧10003給程序計數器PC，出棧n=4給上一層斐波那契函數的n，回到上層的斐波那契函數。
第十一步，執行程序計數器PC指向的指令（內存地址為10003的指令），也就是執行int b=fibonacci(n-1)，是一個函數調用，將下一條指令的地址壓入棧，也就是將10004入棧，此時n=4，將n=4壓入數據棧，此時a=1，將a=1壓入數據棧，傳入的n=3。
第十一步，斐波那契函數中執行到int a=fibonacci(n-2)，將下一條指令的地址壓入棧，也就是將10003入棧，此時的n=3，將n=3壓入數據棧，傳入的n=1。
第十二步，此時n=1，可以直接返回1給上層的斐波那契函數的a，返回的同時出棧10003給程序計數器PC，出棧n=3給上一層斐波那契函數的n，回到上層的斐波那契函數。
第十三步，執行程序計數器PC指向的指令（內存地址為10003的指令），也就是執行int b=fibonacci(n-1)，是一個函數調用，將下一條指令的地址壓入棧，此時n=3，將n=3壓入數據棧，此時a=1，將a=1壓入數據棧，傳入的n=2。
第十四步，此時n=2，可以直接返回1給上層的斐波那契函數的b，返回的同時出棧10004給程序計數器PC，出棧n=3給上一層斐波那契函數的n，出棧a=1給上一層斐波那契函數的a，回到上層的斐波那契函數。
第十五步，執行程序計數器PC指向的指令（內存地址為10004的指令），也就是執行int c=a+b，然后順序執行一直到返回，返回2給上層斐波那契函數的b，返回的同時出棧10004給程序計數器PC，出棧n=4給上一層的斐波那契函數的n，回到上層的斐波那契函數。
第十六步，執行程序計數器PC指向的指令（內存地址為10004的指令），也就是執行int c=a+b，然后順序執行一直到返回，返回3給上層斐波那契函數的b，返回的同時出棧10004給程序計數器PC，出棧n=5給上一層的斐波那契函數的n，出棧a=2給上一層的斐波那契函數的a，回到上層的斐波那契函數。
f(5)=f(3)+f(4)
=[f(1)+f(2)]+[f(2)+f(3)]
=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]
此時紅色部分已通過遞歸計算完成。
第十七步，執行程序計數器PC指向的指令（內存地址為10004的指令），也就是執行int c=a+b，然后順序執行一直到返回，返回5給上層斐波那契函數的接收者，返回的同時出棧15001給程序計數器PC，出棧主函數中的數據（未體現在圖中），回到主函數。
此時斐波那契第五項計算完成。
后記
到了揭曉為什么會爆棧的時刻了，內存中實現函數調用的棧區的大小是有限的，如果遞歸層數太深，入棧的內容越來越多，甚至出現只入棧不出棧的情況（還沒有符合返回條件執行到返回指令棧就滿了），如此進行下去，棧滿、棧溢出、爆棧只是時間問題，因此在實際項目應用中，如果不能估算出遞歸的深度，函數遞歸就要慎用了。
本文雖以斐波那契數列為例介紹函數遞歸調用的底層原理，但在真正的面試中如果面試官問到了斐波那契數列相關的問題，還是不要給面試官回答一個遞歸的解法，原因之一就是當n非常大的時候容易爆棧，原因之二就是文章開頭說的會產生大量的重復計算。在這里我給大家再提一種解法，就是動態規劃（DP）解法。不要一看到動態規劃就害怕，斐波那契數列的動態規劃解法還是很好理解的。先開一個大一些的數組f。
int fibonacci(int n)
{
f[1]=1,f[2]=1;
for(int i=3;i<=n;i++)
{
f[i]=f[i-2]+f[i-1];
}
return f[n];
}
這樣無非是把遞歸變成了循環，但優點是不會出現重復計算。
簡單的遞歸實現求斐波那契數列項的算法底層之復雜是我沒有想象到的，直到一張圖一張圖親手畫出來我才大吃一驚，在這里我要感謝底層硬件工程師的辛勤付出，沒有他們為我們布線鋪路，我們是無法使用高級語言輕松編程的。
本文的介紹本著一切從簡、方便理解的原則，可能有些地方與實際情況有出入，但是基本思想是一樣的。如有不當之處，還請大家批評指正。
