【C语言】函数递归(详解) |
您所在的位置:网站首页 › c语言条件函数怎么用 › 【C语言】函数递归(详解) |
文章目录
函数递归什么是递归?递归的俩个必要条件代码引例1栈溢出(Stack Overflow)
合理使用递归代码引例3代码引例4解释要合理使用递归
结束语
函数递归
程序调用自身的编程技巧称为递归 recursion) 函数自己调用自己就是递归 你也可以理解成是一种嵌套结构,但递归分为俩部分,第一是“递”,进入嵌套结构。第二是”归“,最终会一步一步返回。第一次接触递归都会很懵,慢慢理解这个过程就明白了。 什么是递归?递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接 调用自身的 一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解, 递归策略 只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。 递归的主要思考方式在于:把大事化小 递归的俩个必要条件 代码引例1接受一个整型值(无符号),按照顺序打印它的每一位。 例如: 输入:123,输出 1 2 3 参考代码: #include void print(int n) { if(n>9) { print(n/10); } printf("%d ", n%10); } int main() { int num = 123; print(num); return 0; }运行结果如下: 我们要怎么理解这个函数递归的实现呢 我们可以采用画图方式理解这个过程 所以我们可以看到,递归必须满足俩个必要条件: 1.存在限制条件,当满足这个限制条件的时候,递归便不再继续。 2.每次递归调用之后越来越接近这个限制条件。 题中的限制条件就是(n>9),当我们的n通过(n/10)越来越少,直至n=1,无法满足时,递归停止,并开始返回。 这里有一个重要点就是print(n/10),如果没有这个条件,换成print(n)的话,n一直无法减小,一直进行递归。最后会导致栈溢出(Stack Overflow)。 栈溢出(Stack Overflow)关于栈溢出,我就先简单介绍一下栈 栈:栈是一种计算机系统中的数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来),是一种特殊的线性表。栈的操作常用的有进栈(PUSH),出栈(POP),还有常用的标识栈顶和栈底。 可以把栈想象成一摞扑克牌一样,一张一张叠加起来。 而栈溢出呢是缓冲区溢出的一种,缓冲区溢出:简单的说,缓冲区溢出就是超长的数据向小缓冲区复制,导致数据超出了小缓冲区,导致缓冲区其他的数据遭到破坏,这就是缓冲区溢出。而栈溢出是缓冲区溢出的一种,也是最常见的。只不过栈溢出发生在栈,堆溢出发生在堆,其实都是一样的。 而在代码引例1中 系统分配给程序的栈空间是有限的,但是如果出现了死循环,或者(死递归),这样有可能导致一 直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为栈溢出 合理使用递归使用递归的宗旨是把大事化小 所以遇到问题时,我们应该明白是要把问题简单化,而不是习惯用递归,就一直用递归思考问题 我们应该清楚是不是用递归的思想会比较简单,或者换成递归的思想也可以实现,我们可以通过例题明白 代码引例3求n的阶乘 用循环的方法,代码如下: int main() { int n = 0; int ret = 1; scanf("%d", &n); //循环产生1~n的数字 int i = 0; for (i = 1; i if (n if (n int result = 1; while (n > 1) { result *= n ; n -= 1; } return result; } //求第n个斐波那契数 int fib(int n) { int result; int pre_result; int next_older_result; result = pre_result = 1; while (n > 2) { n -= 1; next_older_result = pre_result; pre_result = result; result = pre_result + next_older_result; } return result; }提示: 许多问题是以递归的形式进行解释的,这只是因为它比非递归的形式更为清晰。 但是这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性稍微差些。 当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销 结束语本人是学c小白,这些是近期学习整理总结,有什么不对欢迎大家指正,我会继续努力,谢谢~! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |