这周看了一道求数组排列的题目,解法用了递归,看懂之后自己对递归的理解更深了。
递归的定义
递归是指程序调用自身,但调用时必须改变调用参数,直到某个参数满足退出条件。函数调用的过程会用到run-time stack,递归时栈中的内容有相似性,但是每一层的差异最终会导致运行栈增长的停止,并且从栈顶返回。
理解递归,最终还是要归结到理解函数调用过程中运行栈的增长和退出。
run-time stack
函数P调用函数Q时,栈顶增长,栈顶的地址向低地址方向移动,寄存器%rsp的值减少。当Q中的代码遇到return子句或者代码全部运行之后Q返回,栈顶退出,函数P恢复调用Q之前的状态,接着运行。
代码演示和解释
#include <stdio.h>
void recursive_ill(int *x, int level) {
if (level == 0) return;
for (int i = 0; i < 10; i++) {
(*x)++;
recursive_ill(x, level - 1);
}
}
int main() {
int x = 0;
recursive_ill(&x, 3);
printf("%d\n", x);
return 0;
}
大家可以先自己思考一下最终打印出来的结果是多少。
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
答案就是1110。我们接下来分析一下这个结果是怎么来的。
这个图片就是上面那段代码的运行时函数调用栈的形式,因为recursive_ill(0)会马上返回,所以没有画出来。
首先,main()调用recursive_ill(3),在recursive_ill(3)中,i=0,(*x)加一,
然后调用recursive_ill(2),在recursive_ill(2),i=0,(*x)加一,
然后调用recursive_ill(1),在recursive_ill(1)中,i=0,(*x)加一,
然后调用recursive_ill(0),马上返回;
此时,recursive_ill(1)恢复,recursive_ill(1)中,i=1,(*x)加一,
然后调用recursive_ill(0),马上返回;
。。。。。。
当在recursive_ill(1)中,i=10时,返回,
此时,recursive_ill(2)恢复,recursive_ill(2)中,i=1,(*x)加一,
然后调用recursive_ill(1),在recursive_ill(1)中,i=0,(*x)加一,
然后调用recursive_ill(0),马上返回;
。。。。。。
当在recursive_ill(2)中,i=10时,返回,
此时,recursive_ill(3)恢复,在recursive_ill(3)中,i=1,(*x)加一,
然后调用recursive_ill(2),在recursive_ill(2),i=0,(*x)加一,
然后调用recursive_ill(1),在recursive_ill(1)中,i=0,(*x)加一,
然后调用recursive_ill(0),马上返回;
。。。。。。
当在recursive_ill(3)中,i=10时,返回,
main()调用printf,打印出x的值。返回,程序结束运行。
总结
我们对上面那个例子的调用过程做个总结:
函数P调用函数Q,当栈顶从函数Q回退到函数P时我们说调用结束。
在上面的代码中,main()调用recursive_ill(3),recursive_ill(3)调用recursive_ill(2),recursive_ill(2)调用recursive_ill(1),recursive_ill(1)调用recursive_ill(0)。
main()对recursive_ill(3)的调用结束时,(*x)在recursive_ill(3)中进行了10次加一,
每一次加一之后都要调用recursive_ill(2),(*x)在recursive_ill(2)中进行了10次加一,
每一次加一之后都要调用recursive_ill(1),(*x)在recursive_ill(1)中进行了10次加一,
每一次加一之后都要调用recursive_ill(0),(*x)没有变化。
所以(*x)在recursive_ill(3)中总共进行10次加一,在recursive_ill(2)中总共进行100次加一,在recursive_ill(1)中总共进行1000次加一。
所以,main()调用recursive_ill(3)结束后,(*x)总共进行1110次加一,如果开始(*x)是0,最终(*x)的值是1110。
ps
文章里面的图片有点少了,请大家对文字多点耐心,理解之后肯定很有帮助。每次的文章都是希望能帮助到大家,尤其是关注我的朋友。