程序員圈流傳這樣一句話：普通程序員用迭代，天才程序員用遞歸。對于編程初學(xué)者來說，別說寫遞歸，就是閱讀遞歸代碼也是很困難的，你是否有這樣的困惑：當我們調(diào)試一段遞歸程序時，發(fā)現(xiàn)它的調(diào)用流程很詭異。如果你理解“棧幀”這樣一個概念，我想你應(yīng)該就能理解遞歸了。

從棧幀說起

什么是棧幀呢？百度百科的解釋是：棧幀就是一個函數(shù)執(zhí)行的環(huán)境。實際上，棧幀可以簡單理解為：棧幀就是存儲在用戶棧上的（當然內(nèi)核棧同樣適用）每一次函數(shù)調(diào)用涉及的相關(guān)信息的記錄單元。
通俗地說，當我們在調(diào)用一個函數(shù)時，就會在內(nèi)存中開辟一段?？臻g，當函數(shù)返回時，?；謴?fù)平衡。然后在調(diào)用另一個函數(shù)時，依此循環(huán)，這樣有限的?？臻g就不斷地執(zhí)行著一個個的函數(shù)。遞歸函數(shù)的執(zhí)行流程跟普通函數(shù)并無二致。初學(xué)編程時我們被告知，遞歸函數(shù)需要一個出口條件，即確認函數(shù)執(zhí)行有限步驟后結(jié)束，現(xiàn)在我們應(yīng)該知道原因了吧：在函數(shù)內(nèi)部再次調(diào)用同個函數(shù)，則每調(diào)用一次函數(shù)即開辟新的一段?？臻g，沒有出口條件，?？臻g就會耗盡，程序崩潰（有些情況下編譯器經(jīng)過優(yōu)化并不會崩潰）。
如果想要了解棧幀的更多底層細節(jié)，需要系統(tǒng)學(xué)習(xí)匯編語言。

• 棧幀.png

二叉樹遞歸遍歷

下面是二叉樹的前序遍歷的代碼，是使用遞歸實現(xiàn)的。

typedef struct TreeNode {
    int data;
    TreeNode * left;
    TreeNode * right;
} TreeNode;
 
void pre_order(TreeNode * Node)//前序遍歷遞歸算法
{
    if(Node == NULL)
    return;
    printf("%d ", Node->data);//顯示節(jié)點數(shù)據(jù)，可以更改為其他操作。
    pre_order(Node->left);
    pre_order(Node->right);
}

對于下圖二叉樹，它的節(jié)點打印順序如序號所示

二叉樹前序遍歷.png

相信讀者對于1->2->4->7這一段流程很好理解。打印7后，執(zhí)行下一行代碼pre_order(Node->left)，這時左子節(jié)點為空，執(zhí)行return。這里就比較難理解了，return到了哪里？我們不知道是因為有些步驟隱藏起來了，要把C語言代碼拆分成更細顆粒度的匯編代碼方能窺見天機。
為了還原實現(xiàn)細節(jié)，我們將上面的程序反匯編（使用Mac平臺Xcode編譯的AT&T匯編），pre_order函數(shù)段如下：

匯編.png

• 幾個概念說明
  • callq 0x100002da0 執(zhí)行時，會將下一條指令入棧
  • retq 執(zhí)行時，會將當前棧頂指令出棧并跳轉(zhuǎn)執(zhí)行。
  • rbp定義為指向當前棧幀棧底的指針，rsp定義為指向當前棧幀棧頂?shù)闹羔?/li>

我們主要關(guān)注對棧幀的變化起關(guān)鍵作用的程序節(jié)點（圖示主要為了展示原理，省略了一些存儲內(nèi)容）：

棧幀變化過程1.png

棧幀變化過程2.png

• 遞歸過程，請對照匯編代碼及棧幀變化過程圖
  1、前面的過程略過，打印7后，逐條指令執(zhí)行到第17行，callq 0x100002da0，這時將下一條指令即第18行0x100002de0指令入棧，然后原rbp棧底地址入棧保存起來，當前rsp賦值給rbp，rsp指針往棧頂方向移動一定空間
  2、這時的入?yún)椋?的左子節(jié)點NULL，執(zhí)行到第8行時，跳轉(zhuǎn)到0x100002ded（第21行）
  3、這時會開始回退到上一個棧幀，rsp恢復(fù)指向棧底，rbp出棧并恢復(fù)原值（即上一個棧幀的棧底地址），retq執(zhí)行，將當前棧頂指令第18行0x100002de0出棧并跳轉(zhuǎn)執(zhí)行
  4、取參數(shù)7的右子節(jié)點NULL，第20行 callq 0x100002da0 ，對應(yīng)C語言程序pre_order(Node->right)，這時將第21行0x100002ded指令入棧，原rbp棧底地址入棧（第21至24行這段指令操作在C語言中是沒有對應(yīng)語句的，也就是說C語言無法單獨表達這一段操作，正是這個表達缺陷造成了遞歸理解的困難）
  5、繼續(xù)逐條執(zhí)行指令，因為當前入?yún)镹ULL，執(zhí)行到第8行時，跳轉(zhuǎn)到第21行0x100002ded，這時rbp恢復(fù)上一次保存的值，回退到圖中編號6棧幀棧底，然后retq 執(zhí)行，跳轉(zhuǎn)第21行0x100002ded指令
  6、繼續(xù)退回到上一個棧幀，此時rbp指針指向編號3棧幀的棧底，接著pop并執(zhí)行棧頂指令第14行0x100002dd0，開始執(zhí)行對應(yīng)C語言代碼 pre_order(Node->right)
  7、接下來第21行0x100002ded入棧，接著打印8，8的左子節(jié)點為NULL …… rbp指向編號8棧底，pop并跳轉(zhuǎn)到0x100002de0（第18行）
  8、此時8的右子節(jié)點為NULL，返回哪里取決于當初callq保存的下一條指令，即執(zhí)行第21行0x100002ded，退回到編號3棧幀，由于保存的下一條指令為第21行0x100002ded，繼續(xù)回退到編號2棧幀。
  9、后面的流程就留給讀者自己梳理。

如果現(xiàn)在你還是有點懵，那么二叉樹的前序遍歷還有一種非遞歸的實現(xiàn)，就是模擬的遞歸過程，代碼如下：

二叉樹前序遍歷非遞歸實現(xiàn)

（以下代碼摘抄自 二叉樹的非遞歸遍歷（前序中序后序非遞歸C語言） ）

#include <stdio.h>
#include <stdlib.h>
#define M 100 
typedef struct node  
{  
    int data;
    struct node *lchild;  
    struct node *rchild;  
}bitree;
 
typedef struct stack 
{
    bitree *elements[M];
    int top;
}seqstack;//定義一個儲存樹類型地址的棧，方便遍歷的時候追蹤到樹的地址。

bitree *root;//定義一個樹根
seqstack s;//定義棧

void setnull()//初始化棧
{
    s.top =0;
}
 
void push(bitree *temp)//入棧操作
{
    s.elements[s.top++] = temp;
}
 
bitree *pop()//取棧頂并出棧頂
{
    return s.elements[--s.top];
}
 
int empty()//判斷空棧
{
    return s.top == 0;
}
 
bitree *creat()   /*建立二叉樹的遞歸算法*/
{ bitree *t;
  int x;
  scanf("%d",&x);
  if(x==0) t=NULL; /*以x=0表示輸入結(jié)束*/
  else{
  t=(bitree*)malloc(sizeof(bitree));//動態(tài)生成結(jié)點t,分別給結(jié)點t的數(shù)據(jù)域、左右孩子域  
  t->data=x;                  //賦值,給左右孩子域賦值時用到了遞歸的思想。
  t->lchild=creat();
  t->rchild=creat();
  }
  return t;
}

void preorder(bitree *t)//前序遍歷的非遞歸算法
{
    bitree *temp = t;//定義一個樹節(jié)點，用它來遍歷
    while(temp != NULL || s.top != 0)
    {
        while(temp != NULL)//先遍歷左孩子，并輸出。
        {
            printf("%4d",temp->data);
            push(temp);
            temp = temp->lchild;
        }
        if(s.top != 0)//當左孩子遍歷完后，取棧頂，找右孩子。此時循環(huán)還沒有結(jié)束，再遍歷它的左孩子，直至孩子全部遍歷結(jié)束。
        {
            temp = pop();
            temp = temp->rchild;
        }
    }
    printf("\n");
}

int main()
{
    bitree *root;//創(chuàng)建根
    setnull();//制空棧
    root=creat();//創(chuàng)建二叉樹:嘗試輸入：1 2 4 7 0 0 8 0 0 0 3 5 0 9 0 0 6 0 0
    printf("前序遍歷:\n");
    preorder(root);
    return 0;
}

結(jié)合非遞歸的實現(xiàn)方式，我們就能更加容易理解遞歸了。

總結(jié)

函數(shù)調(diào)用機制巧妙地利用棧這樣一個數(shù)據(jù)結(jié)構(gòu)，調(diào)用函數(shù)時將下一條指令存起來，返回時再取出執(zhí)行目標指令。我們了解了函數(shù)調(diào)用過程中的棧幀入棧、出棧原理，也就能理解遞歸了。我們此前的困惑主要是不清楚return時的返回路徑，經(jīng)過上面遞歸的分析和理解，可以這樣抽象：如果遞歸函數(shù)內(nèi)部的遞歸函數(shù)調(diào)用是函數(shù)體的最后一個動作，則該函數(shù)調(diào)用時將下一步操作“退回上一層”入棧。反之，如果不是函數(shù)體的最后動作，則該函數(shù)調(diào)用時將下一步操作入棧，這樣在返回時根據(jù)當層存儲的操作來執(zhí)行下一步。