代码顺序存储，逐条执行。
代码的控制结构（if, while, for, continue, break, return），可以进行跳转。

函数调用机制也是一种控制结构机制，因为每个函数有一条显式或隐式的return语句。

1 函数的调用与return机制

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

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

2 递归函数的参数迭代与循环的对应关系

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

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

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

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

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

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

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

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

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

int factRecur(int n){  // 阶乘递归版
    if(n<=1)
        return 1;
    return n*factRecur(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。

4 双递归

双递归，一个函数在函数体内有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 5

int 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－