C语言递归
沙漠下的胡杨 人气:0递归的认识
基本认识:
1.首先递归的本质还是函数调用,也要形成和释放栈帧。
2.函数的调用是有成本的,这个成本在时间和空间上表现为函数栈帧的形成和销毁。
3.递归就是 不断形成栈帧和销毁的过程。
理论认识:
1.内存和cpu中的资源有限,也就决定啦,合理的递归是绝对不可以无限递归下去的。
2.递归不是什么时候都可以使用的,而是要满足自身的场景,即目标函数的子问题可以用该算法解决,本质是分治的思想。
3.递归的核心:大事化小,递归出口。
main函数可以递归吗
相信有些读者就在疑惑啦?main函数是主函数呀,这个怎么可以自己调用自己呢?
实际上,main函数本质也是函数,所以也就会形成栈帧,所以是可以自己调用自己的。
代码和运行结果如下:
int main() { printf("胡杨树下\n"); Sleep(100);//睡眠0.1秒 main(); return 0; }
结果显示是可以调用的,那么我们也能过看出来,这个main函数的递归是不会自动停止的,停止时就是发生栈溢出,那么函数的栈帧是怎么形成的呢?
是最下面的main函数进行调用自身形成栈帧,如图示,我们可以看出,这些函数调用都开辟了空间,所以要占用内存,而且形成栈帧后需要释放,形成和释放过程中有时间消耗。这也就是递归有成本的原因。
递归核心思想讲解
我们在平时中见过这个题目,叫做求字符串长度。
这个我们可以用递归的写法求解,顺带我们看下递归的核心。
首先假设我们求的字符为 "abcdefg123",我们用递归的解法可以转化为,1+"bcdefg123",把"bcdefg123"进而再转化为1+"cdefg123",进行求解,如图示:
经过一次次的大事化小,我们最后把问题变成了,求1+空字符串的长度,这个其实也就是我们想要的递归出口,当没有字符时我们就该结束啦。
代码如下:
int My_strlen(const char *str) { if (*str == '\0')//函数出口 { return 0; } return 1 + My_strlen(str + 1);//继续 } int main() { int len = My_strlen("abcdefg123"); printf("len = %d\n", len); return 0; }
递归的缺点
我们来看下递归的另外一个经典例子,第n个菲波那切数列的实现
首先菲波那切数列是前两个数之和等于第三个数,第一个和第二个我们设定为1,那么这个数列为 1,1,2,3,5,8,13....等等,那我们要求第n个斐波那契数列的话,只要转化为求前两个数的和就好了,最后的递归出口为第一个或者第二个数时停止,结束函数。
代码如下:求第十个菲波那切数
int fib(int n) { if (n == 1 || n == 2) { return 1; } return fib(n - 1) + fib(n - 2); } int main() { printf("fib(%d) = %d\n", 10, fib(10)); return 0; }
我们如果求的 n 的数字比较大就会非常慢。这个本质就是上述说的成本问题。
如果求的是第42个菲波那切数呢?这次我们把时间也计算上。
int fib(int n) { if (n == 1 || n == 2) { return 1; } return fib(n - 1) + fib(n - 2); } int main() { int n = 42; double start = GetTickCount(); int x = fib(n); double end = GetTickCount(); printf("fib(%d) = %d count = %.1f S\n", n,x,(end - start)/1000); return 0; }
我们可以看出第42个时就已经10秒了,这个很长时间啦。我们用全局变量接收下次数,那我们看看他计算了多少次第3个菲波那切数计算了几次? 计算了大概1亿多次,所以递归的重
复计算是非常多的。
我们看个图示:
其中单单是第六个菲波那切数就计算了3次,这个就很夸张啦。
所以递归的特点是代码简单,但是调用上可能会有大的成本。
最后一点就是:循环和递归是一定可以相互转化的。只不过有些时候转化会比较麻烦。
加载全部内容