今天分享的是递归算法,为了后面的二叉树做铺垫。递归是一种非常重要的算法,应用递归算法,可以方便的解决很多问题。但是递归分析起来可能会觉得非常绕,一不小心就出不来了。递归说白了就是自己调用自己,关于递归,有几点需要特别注意的地方:
1、递归的终止条件是什么?递归一定需要终止条件,否则就变成了死循环。
2、递归的最后一次是什么情况?
3、一次递归完成了什么事情?
下面是求阶乘的递归图,可以看到,递归需要一层层的进去,遇到终止条件之后还需要一层层的出来。
下面通过例子来讲解关于递归的一些操作。
#include<stdio.h>
void test(int n)
{
if(n<0){
return;
}
printf("%d ",n);
test(n-1);
}
int main()
{
test(2);
}
在这个例子里面,相信大家很容易可以得出执行的结果是2,1,0。这个没有什么难度。
如果把printf("%d ",n);放在test(n-1)的后面呢?
void test(int n)
{
if(n<0){
return;
}
test(n-1);
printf("%d ",n);
}
估计有人开始犹豫了,应该打印出什么?打印出-1吗?当然不是。结果是0,1,2。
这里只是把打印语句和递归函数调了一下位置,结果就倒过来了。
为什么结果是这样子的呢?可以这样分析:
首先主函数调用test(2)的时候,我们如果不考虑递归,应该是执行
//伪代码,只表示含义
test(1);
printf 2;
这样就执行完了,只不过由于这个是递归,应该要把test(1)给展开,展开成test(0) 和printf 1;
这样还不够,还得把test(0)展开,展开成test(-1)和printf 0;
通过这样层层展开,就知道最先打印的是0,然后是1,最后是2。
通过以上分析可以知道,递归是有先序递归和后序递归之分,这两种递归的结果刚好是逆序的。
接下来继续增加难度:
#include<stdio.h>
void test(int n)
{
if(n<0){
return;
}
printf("%d ",n);
test(n-1);
printf("#%d ",n);
test(n-1);
printf("*%d ",n);
}
int main()
{
test(2);
}
如果能把这个打印结果理清楚,那么就说明对递归有一定理解了。
这里面有两次调用递归,在递归前后都加了打印语句,打印语句里面加上#和*符号用来区分是哪个地方打印的。
估计可以比较容易想到最先打印的肯定是2,1,0。但是打印完2 1 0 之后应该打印什么?好像应该往下执行printf("#%d ",n)语句,但此时的n究竟是多少?
如果这样思考很容易陷进去,然后就不知道怎么出来了。先把结果放在这里,看结果和你想的是不是一样的。
打印出来了一串数字。其实分析方法还是用刚刚的展开法就很好做,按照展开法,应该是:
printf 2;
test(1);
printf #2;
test(1);
printf *2;
这就是整个过程,接下来只要把里面的test(1)用同样的方法展开,就可以知道为什么是上面的打印结果了。
这就是涉及到两层递归的时候,用展开法还是非常好分析,同时也得出一些经验:遇到递归不要立马带进去算,因为现在就带进去容易把后面的忘记,而且你也不知道究竟有多少层才能结束。我们只要把递归当作一个标号一样,先记录一下,然后把后面的执行完,等后面所有的都执行完了之后,再把里面的递归一层层展开,这样就可以做到不重不漏,而且不会把自己陷进去。
以上就是关于递归的一些分析方法。