程式调用本身的编程技巧称为递归( recursion)。 程序员圈撒播这样一句话：To iterate is human,to recurse divine. 迭代是人，递归是神。对于编程初学者来说，甭说写递归，就是阅览递归代码也是很困难的，你是否有这样的困惑：当咱们调试一段递归程序时，发现它的调用流程很诡异。假如你了解“栈帧”这样一个概念，我想你应该就能了解递归了。

从栈帧说起

什么是栈帧呢？百度百科的解释是：栈帧就是一个函数履行的环境。实际上，栈帧能够简略了解为：栈帧就是存储在用户栈上的（当然内核栈相同适用）每一次函数调用涉及的相关信息的记载单元。 通俗地说，当咱们在调用一个函数时，就会在内存中拓荒一段栈空间，当函数回来时，栈康复平衡。然后在调用另一个函数时，依此循环，这样有限的栈空间就不断地履行着一个个的函数。初学编程时咱们被告知，递归函数需求一个出口条件，即确认函数履行有限进程后完毕，现在咱们应该知道原因了吧：在函数内部再次调用同个函数（也就是递归），则每调用一次函数即拓荒新的一段栈空间，没有出口条件，栈空间就会耗尽，程序溃散（尾递归通过编译器优化可防止溃散）。

假如想要了解栈帧的更多底层细节，能够体系学习汇编言语。

咱们将以一个二叉树的递归为例，来阐明递归的履行原理。

二叉树递归

下面是二叉树的前序遍历的代码，是运用递归完成的。

typedef struct TreeNode {
    int data;
    TreeNode * left;
    TreeNode * right;
} TreeNode;
void pre_order(TreeNode * Node)//前序遍历递归算法
{
    if(Node == NULL)
    return;
    printf("%d ", Node->data);//显现节点数据，能够更改为其他操作。
    pre_order(Node->left);
    pre_order(Node->right);
}

对于下图二叉树，它的节点打印次序如序号所示

相信读者对于1->2->4->7这一段流程很好了解。打印7后，履行下一行代码pre_order(Node->left)，这时左子节点为空，履行return。这里就比较难了解了，return到了哪里？咱们不知道是因为有些进程隐藏起来了，要把C言语代码拆分成更细颗粒度的汇编代码方能窥见天机。 为了复原完成细节，咱们将上面的程序反汇编（运用Mac渠道Xcode编译的AT&T汇编），pre_order函数段如下：

反汇编剖析

• 几个概念阐明
  • callq 0x100002da0 履行时，会将该条指令后的下一条指令入栈
  • retq 履行时，会将当时栈顶指令出栈并跳转履行。
  • rbp界说为指向当时栈帧栈底的指针，rsp界说为指向当时栈帧栈顶的指针

咱们主要重视对栈帧的改变起关键作用的程序节点（图示主要为了展现原理，省掉了一些存储内容）：

栈帧改变进程1

栈帧改变进程2

递归进程，请对照汇编代码及栈帧改变进程图

1、前面的进程略过，打印7后，逐条指令履行到第17行，callq 0x100002da0，这时将下一条指令即第18行0x100002de0指令入栈，然后原rbp栈底地址入栈保存起来，当时rsp赋值给rbp，rsp指针往栈顶方向移动必定空间

2、这时的入参为：7的左子节点NULL，履行到第8行时，跳转到0x100002ded（第21行）

3、这时会开端回退到上一个栈帧，rsp康复指向栈底，rbp出栈并康复原值（即上一个栈帧的栈底地址），retq履行，将当时栈顶指令第18行0x100002de0出栈并跳转履行

4、取参数7的右子节点NULL，第20行 callq 0x100002da0 ，大致对应C言语程序pre_order(Node->right)，这时将第21行0x100002ded指令入栈，原rbp栈底地址入栈（第21至24行这段指令操作在C言语中是没有对应句子的，也就是说C言语无法独自表达这一段操作，正是这个表达缺陷造成了递归了解的困难）

5、持续逐条履行指令，因为当时入参为NULL，履行到第8行时，跳转到第21行0x100002ded，这时rbp康复上一次保存的值，回退到图中编号6栈帧栈底，然后retq 履行，跳转第21行0x100002ded指令

6、持续退回到上一个栈帧，此刻rbp指针指向编号3栈帧的栈底，接着pop并履行栈顶指令第14行0x100002dd0，开端履行对应C言语代码 pre_order(Node->right)

7、接下来第21行0x100002ded入栈，接着打印8，8的左子节点为NULL …… rbp指向编号8栈底，pop并跳转到0x100002de0（第18行）

8、此刻8的右子节点为NULL，回来哪里取决于最初callq保存的下一条指令，即履行第21行0x100002ded，退回到编号3栈帧，由于保存的下一条指令为第21行0x100002ded，持续回退到编号2栈帧。

9、后边的流程就留给读者自己整理。

假如现在你还是有点懵，那么二叉树的前序遍历还有一种非递归的完成，就是模仿的递归进程，代码如下：

二叉树前序遍历非递归完成

（以下代码摘录自 二叉树的非递归遍历（前序中序后序非递归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表示输入完毕*/
  else{
  t=(bitree*)malloc(sizeof(bitree));//动态生成结点t,分别给结点t的数据域、左右孩子域  
  t->data=x;                  //赋值,给左右孩子域赋值时用到了递归的思维。
  t->lchild=creat();
  t->rchild=creat();
  }
  return t;
}
void preorder(bitree *t)//前序遍历的非递归算法
{
	bitree *temp = t;//界说一个树节点，用它来遍历
	while(temp != NULL || s.top != 0)
	{
		while(temp != NULL)//先遍历左孩子，并输出。
		{
			printf("%4d",temp->data);
			push(temp);
			temp = temp->lchild;
		}
		if(s.top != 0)//当左孩子遍历完后，取栈顶，找右孩子。此刻循环还没有完毕，再遍历它的左孩子，直至孩子全部遍历完毕。
		{
			temp = pop();
			temp = temp->rchild;
		}
	}
	printf("\n");
}
int main()
{
	bitree *root;//创建根
	setnull();//制空栈
	root=creat();//创建二叉树:尝试输入：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;
}

结合上述履行流程，咱们就能愈加容易了解递归了。

总结

函数调用机制奇妙地使用栈这样一个数据结构，调用函数时将下一条指令存起来，回来时再取出履行方针指令。咱们了解了函数调用进程中的栈帧入栈、出栈原理，也就能了解递归了。咱们此前的困惑主要是不清楚条件停止时return的回来途径，通过上面临递归的剖析和了解，笔者认为递归能够这样笼统：假如递归函数内部的递归函数调用是函数体的最终一个动作，则该函数调用时将下一步“隐性”操作“退回上一层”入栈。反之，假如不是函数体的最终动作，则该函数调用时将代码上下文的下一步操作入栈，这样在teturn时依据当层存储的操作来决策履行。