递归调用
void rec(int N) {
//为了区分这两个递归,分别为它们取个别名好了
if (N>0){
rec(N - 1);//rec1
rec(N - 10);//rec2
}
cout << "N=" << N << endl;
cout << "最后一句了" << endl;
}
第一步:前11次递归肯定是只有rec1进行递归入栈,这是毋容置疑的,入栈之后就是下面这个样子了
第二步:rec1递归完之后,开始出栈。第一次出栈得到N=0,判断N是否满足递归条件,当然以后每次出栈之后都是要判断一次的,毕竟还要进行一次递归。显然N=0不满足递归条件,直接跳到后面的两个cout语句去。这样就完成了第一次出栈操作。
第三步:rec1的第二次出栈,取到的元素是1,即N=1,注意这个时候并没有将栈顶元素1删除。在rec1处取到元素之后,继续往下执行,到了rec2递归语句这里了,这个时候会中断rec1的出栈操作,转而去执行rec2的入栈操作,所以进入rec2递归入栈,此时入栈的元素是-9 (因为1-10=-9),很显然此时已经不满足再次入栈的条件了,那rec2会直接出栈,出栈元素就是-9,跳到后面的去执行cout语句,栈的变化过程如下所示:
第四步:前面说到rec1是中断自己的操作去先执行rec2的,那么现在rec2执行完了,那rec1就可以继续它的出栈操作了,所以此时N的值就变成了1,即N=1,然后继续往下执行,也就是执行到了cout操作,完成了rec1的第二次出栈操作。此时栈就变成了下面的样子了:
最后rec1完成第二次出栈后,继续执行rec1出栈操作,重复以上步骤。上面说了那么多,其实就是按代码来顺序执行。
下面的是出栈的入栈的过程:
用下面的代码来解释一下按代码顺序来执行是什么意思:
void rec(int N) {
if (N>0){
rec(N - 10);//rec1
rec(N - 1);//rec2
}
cout << "N=" << N << endl;
cout << "最后一句了" << endl;
}
输出结果:
这段代码很明显,rec1每次都只能压栈1次,而且我们仔细观察输出结果会发现,前面的0~-9其实都是由rec1进行压栈和出栈的。究其原因,前面说过了,是按代码顺序来执行的,rec2每次压栈之前都要经过if语句判断,然后执行rec1,而且是rec1先执行完,然后才能轮到rec2;而到了后面0~9的输出,那是因为rec2后面直接就是cout语句了,而且出栈操作时,每次都是从需要出栈的语句(rec2)处开始往下执行,所以是连续的输出0~9。