函数调用机制也是一种掌握构造机制，由于每个函数有一条显式或隐式的return语句。

函数都有一条或多条显式的return语句，或一条隐式的return语句（void函数，实行到函数体末了一句时，会隐式实行一条return语句，对应汇编的ret指令）。

函数调用，也便是主调函数（caller）调用被调函数（callee），调用时，代码跳转，离开主调函数caller，实行callee函数体，碰着return语句或实行完函数体后，return回caller的调用点，有返回值的返回给caller中的变量。
callee return回caller调用点便是跳转，能准确跳回是由于存储了一个调用点的地址。
这是编译器背后的支持，通过一个栈机制保存了调用点地址（每次调用都会在栈空间内开辟一个栈帧空间给函数）。
当有嵌套调用时，能逐级调用，逐级返回。
若何逐级返回？便是先返回到最近存储的调用点，也便是后进先出。
犹如你从A点出发，经由n个路口，每经由一个路口，用一张扑克牌记录好须要返回的路口，每过一个路口，记录一张牌，放在前面一张牌的上面，末了要返回时，读取最上面的牌上的返回地址，依次返回。
这些牌依次叠起来，依次从上面拿牌，十分类似函数嵌套调用时的栈帧机制。

递归函数便是自己调用自己。

同样的代码按约定条件重复实行n次，完备可行。
这样一个洋葱，层层相套，代码量一样，实行代码的顺序和代码量可能不一样，问题规律可能逐层递减，参数可能不断迭代变革。

写代码时，对有重复利用代价的功能代码模块可以抽象出函数（包括抽象出函数参数和返回值）。
在调用点调用时，可以想象为适当处理好函数参数和返回值后，将函数体扩充到该位置。
递归调用也是如此，便是将自己的函数体扩充到自己的调用点（可能也有参数迭代）。

嵌套调用可以想象为嵌套膨胀，或嵌套套容器。

如果递归调用了几次，可以理解为将代码重复次。

其余要把稳代码的实行顺序，常日按先后顺序，以调用点（也是返回点）为基准，分为三部分：a 调用点前的代码，在递推阶段实行，常日有一个if语句，也有可能包含一个return语句，提前return。

b 调用点处的调用代码，是调用点（跳转点），也是回归点（return回）。

c 调用点后的代码，在回归阶段实行，直到return语句或函数体末了一条语句，如果是尾递归，则没有这一部分。
如果不是尾递归，历史的局部变量与实参值保存在返回的栈桢上（犹如上述记录的扑克牌），如果递归函数用循环同等实现时，是须要一个额外的栈数据构造来赞助保存这些历史的实参与局部变量。

有一点奇妙之处在于参数的迭代及与循环的对应关系。
为什么迭代函数内只有if语句，却可以构成循环？理解一下递归函数，同行功能实现的循环实现及对应的goto实现就知道了。

int factRecur(int n){ // 阶乘递归版 if(n<=1) return 1; return nfactRecur(n-1); // 递归调用时，参数迭代：n = n-1}int factLoop(int n){ // 阶乘循环版 int sum = 1; while(n>1) sum = n--; return sum;}int factGoto(int n){ // 阶乘goto版 int sum = 1;loop: if(n<=1) goto end; sum = n--; goto loop;end: return sum;}3 单递归

单递归，一个函数只有1次调用自己。
求阶乘便是范例的单递归。
单递归如果是尾递归时，用循环替代时，比较大略，不须要栈数据构造赞助。
如果不是尾递归，须要栈数据构造来赞助记录函数参数（如果有）和局部变量。

单递归是一种线性的call和return。

双递归，一个函数在函数体内有2次调用自己的语句。
汉诺塔和斐波那契数列都是范例的双递归。

二递归对应一棵二叉树，递推和回归（return）的顺序，便是二叉树的深度优先遍历。

二叉树深度优先遍历，一个节点的代码三次进入，三次return回：

非叶节点：3次递推进入和3次return回的机会（叶子节点只有一次机会，碰着基准条件即返回）。

void midOrder(struct treeNode tree) // void函数默认一个return{ if(tree!=NULL) // 非空时递归，空时return回 { // printData(tree);// 写在前面便是前序遍历，第1次进入时操作 midOrder(tree->LChild); // 叉1 参数迭代，回溯时往下走 printData(tree);// 写在中间便是中序遍历，第2次进入时操作 midOrder(tree->RChild); // 叉2 // printData(tree);// 写在后面便是后序遍历，第3次进入时操作 }}

可以理解为代码的重复：

总结一下：递归函数调用自己2次，二叉，加上自己，代码要重复实行3次，三次被call，三次return，形成3个调用和回归点。

5 三递归

三递归，一个函数3次调用自己。

示例代码：

#include <stdio.h>void r(int n){ if(n<=0) //printf("\n__%d__\n",n); return; r(n-3); r(n-2); r(n-1); printf("%d ",n);}int main(){ r(5); return 0;}

形成三叉树的调用关系：

后序遍历，及4次进入的机会。

如r(1)，

第1次：调用r(-2)，再return到r(1)；

第2次：调用r(-1)，再return到r(1)；

第2次：调用r(0)，再return到r(1)；

完全的三叉树：

三叉树深度优先遍历，一个节点的代码四次进入，四次return回：

6 更多次递归函数

如分书问题：

#include <iostream>using namespace std;#define NUMS 5int like[NUMS][NUMS]={ // like[i][j] = 1 表示第i人喜好第j本书 {0,0,1,1,0}, {1,1,0,0,1}, {0,1,1,0,1}, {1,0,0,1,0}, {0,1,0,0,1}};int take[NUMS]={0,0,0,0,0}; // 记录每一本书的分配情形int n = 0; // n表示分书方案数void trynext(int i);int main(){ trynext(0); // 书（列）1-5，人1-5 ，A-E cin.get(); return 0;}void trynext(int j) // 对第 j 本书进行分配{ for(int i=0;i<NUMS;i++) // 对每个人进行穷举 if(like[i][j]&&take[i]==0) { take[i]=j+1; // 把第i本书分配给第j个人 if(j==NUMS-1) // 第NUMS本书分配结束，也即所有的人已经分配完毕， { // 可以将方案进行输出 n++; cout<<"分配方案"<<n<<":"<<endl; for(int k=0;k<NUMS;k++) cout<<"人"<<k<<"→"<<"分到第"<<take[k]<<"本书"<<endl; cout<<endl; } else{ cout<<j+1<<" "; // 调用时的参数记录，赞助理解形成了几次调用关系 trynext(j+1); // 递归，对下一个人进行分配 } take[i]=0; // 回溯，探求下一种方案 }}/1 2 3 4 分配方案1:人0→分到第3本书人1→分到第1本书人2→分到第2本书人3→分到第4本书人4→分到第5本书2 3 4 分配方案2:人0→分到第3本书人1→分到第1本书人2→分到第5本书人3→分到第4本书人4→分到第2本书3 4 4 1 2 3 3 4 分配方案3:人0→分到第4本书人1→分到第2本书人2→分到第3本书人3→分到第1本书人4→分到第5本书2 3 2 3 3 4 分配方案4:人0→分到第4本书人1→分到第5本书人2→分到第3本书人3→分到第1本书人4→分到第2本书/

如果是5个人5本书，由于有回溯的情形，一个分配方案的递归函数，可能多于或小于4递归。

－End－