[toc]
递归
一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的
首先你要理解函数调用的本质:
保存当前
指令地址
跳转到被调用函数(指令段)的起始地址实际过程比这个复杂, 比如还包括保存临时变量和传参等等, 但是对我们正在讨论的问题不起到本质影响所以省略掉不谈
函数调用并不是在原地展开代码
每一个函数都是一段独立存在于存储器中的指令序列
每个程序的内存空间中都包括一个叫做"栈(stack)"的区域, 它的特点是先进后出, 就像一摞书, 只能往顶端放书, 也只能从顶端取书每当你调用一次函数, 就会向栈中压入(push)返回地址, 当函数返回(return)时从栈中弹出(pop)返回地址并跳转回返回地址.
所以, 自身调用乃至循环调用形成的递归调用在进行时, 就会不断压栈来保存函数运行状态, 当递归一层一层返回时, 则是不断出栈了函数调用并不是在原地展开代码
单次调用递归
- 示例一
函数:
void func(int N){
N++;
if (N>2){
return;
}else{
printf("%d\n",N);
func(N);
}
}
调用:
func(0);
打印
1
2
分析 :
- N=1,先打印1,入栈.
- N=2,先打印2,入栈.
- N=3,开始出栈.
- 函数执行完毕
栈有几个 这里会走几次,表示正在出栈
4e1859f1fc53386049ad2821fbf9130d
- 示例二
void func(int N){
N++;
if (N>2){
return;
}else{
func(N);
printf("%d\n",N);
}
}
打印
2
1
分析:
-
N=1,入栈
-
N=2,入栈
-
N=3,不入栈,直接出栈
-
栈顶,N=2,要出栈,但是并没有出栈,而是执行下面的打印,打印完后出栈,N=2也出栈
-
栈顶,N=1,要出栈,但是并没有出栈,而是继续执行打印,打印完出栈,N=1出栈,函数执行完毕.
-
示例三
void func(int N){
N++;
if (N>2){
return;
}else{
func(N);
}
printf("%d\n",N);
}
打印
2
1
分析,和示例二一样
两次调用递归
- 示例一
void func(int N){
N++;
if (N>2){
return;
}else{
printf("%d\n",N);
func(N);
func(N);
}
}
- 打印
1
2
2
分析
- N=1,N=2,入栈之前都会先打印1,2
- N=3,不满足递归条件,跳出
- N=2,要出栈,但是不是先出栈而是走下面的函数
func(N); - 但是N=2,又是得到N++=3,出栈,然后N=2也出栈,
- N=1,要出栈,也是先走下面
func(N), - N=1,N++=2 ,入栈,先打印2
- 然后N=2,上下函数都是N=3,出栈,然后
N=1出栈,函数执行完毕
- 示例二
void func(int N){
N++;
if (N>2){
return;
}else{
func(N);
printf("%d\n",N);
func(N);
}
}
- 打印
2
1
2
分析
- N=1,N=2,入栈
- N=3,不满足出栈,跳出
- 栈顶N=2,出栈,但是并没有先出栈,先
打印2,并执行下面函数func(N),得到N=3,不满足,直接出栈. -
N=2出栈然后出栈. - 接着N=1开始出栈,继续先
打印,在执行函数func(N). - 函数执行得到N++2,满足入栈,然后调上面 func(N),不满足入栈直接出栈,继续调用
打印,然后,调用下面 func(N),不满足直接出栈, -
N=1出栈.函数执行完毕.
最后这个执行两次分别是下面函数N=2时不满足出栈,和之前要出栈有执行打印和函数的那个N=1出栈.
160bc11cf1b39933297afdacc25fd5ea
- 示例三
void func(int N){
N++;
if (N>2){
return;
}else{
func(N);
func(N);
printf("%d\n",N);
}
}
- 打印
2
2
1
-
分析
-
N=1,N=2,依次入栈.
-
N=3,不满足入栈条件,跳出;
-
当N=2要出栈,但是没有先出栈,先执行
func(N);, -
得到N++=3,不满足直接跳出,然后执行打印;
-
然后N=2出栈,得到N=1;
-
执行下面函数func(N).
-
执行上面函数得到N=2,又调到下面函数,下面函数执行到N=3跳出,直接打印,打印执行完出栈,N=1出栈,最后打印1;
- 出栈,后面有函数,会先执行,执行完才出栈,
网友评论