程序运行

指令

1. 指令的划分以函数为单位，
2. 调用函数本质上是使用call指令将pc指针移动到被调用的函数
3. 函数调用完成，需要使用return返回，本质是pc移回调用函数位置

数据

1. 函数调用时，在堆栈区域要申请一片栈帧，函数的局部变量、参数都分配在栈帧上面
2. 函数返回时，堆栈上的栈帧需要释放
3. 栈帧的分配和释放遵循后进先出的原则，即逻辑结构为栈

函数调用自身——递归关注的要点

1. 如何从大问题逐级化成小问题——>转移
2. 如何解决最小问题———————>出口（假设n-1各）

例题

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
long long func(int i){
    if (i==1){
        return 1;
    }
    return i* func(i-1);
}
int main() {
    int i;
    scanf("%d",&i);
    printf("%lld",func(i));
    return 0;
}

例题

分析

设一共有n个盘子，已经完成了n-1个盘子的移动，其中，假设移动n个盘子需要F(n)时间，那么移动n-1个盘子需要F(n-1)时间，那么移动最后第n个盘子时，应该进行如下的步骤：（从左到右是ABC杆）

1. 将n-1个盘子从A杆移动到C杆——需要F(n-1)时间；
2. 将第n个盘子从A杆移动到B杆——需要1时间；
3. 将n-1个盘子从C杆移动到A杆——需要F(n-1)时间；
4. 将第n个盘子从B杆移动到C杆——需要1时间；
5. 将n-1个盘子从A杆移动到C杆——需要F(n-1)时间；

因此有：F(n)=3*F(n-1)+2，得到递推公式，容易得到的是F(1)=2，那么代码就好写了

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
long long func(int i){
    if (i==1){
        return 2;
    }
    return 3* func(i-1)+2;
}
int main() {
    int i;
    while (scanf("%d",&i) != EOF){
        printf("%lld",func(i));
    }
    return 0;
}