1递归是什么递归是一种解决问题的方法在C语言中递归就是函数自己调用自己。一个最简单的C语言递归代码这个代码只是拿来示范的虽然这个代码能运行但是代码最终也会陷入死递归导致栈溢出stack overflow。1.1递归的思想真正的递归是把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。所以递归的思考方式就是把大事化小的过程。递归中的递就是递推的意思归就是回归的意思。1.2递归的限制条件递归在书写的时候有2个必要条件递归存在限制条件当满足这个限制条件的时候递归就不再继续每次递归调用之后越来越多接近这个限制条件2.递归举例2.1举例1求n的阶乘一个正整数的阶乘是所有小于及等于该数的正整数的积并且0的阶乘为1。自然数n的阶乘写作n。题目计算n的阶不考虑溢出n的阶乘就是1~n的数字累积相乘。2.1.1分析和代码实现n的阶乘的公式nn*n-1从上述中不难看出我们想要算出5的阶乘就要先算出4的阶乘想要得到4的阶乘就要先得到3的阶乘以此类推。就是把一个较大的问题转换为一个与原问题相似但规模较小的问题来求解的。n的阶乘和n-1的阶乘是相似的问题但是规模要少了n。有一种特殊情况是当n0的时候n的阶乘是1而其余n的阶乘都是可以通过上面的公式计算。为了展示更加清楚我将以图片的形式进行展示2.2举例2顺序打印一个整数的每一位输入一个整数m按照顺序打印整数的每一位。比如输入1234 输出1 2 3 4输入520 输出5 2 02.1.1分析和代码实现这个题目放在我们面前首先想到的是怎么得到这个数的每一位呢如果n是一位数n的每一位就n自己n是超过1位数的话就得拆分每一位1234%10就能得到4然后1234/10得到123这就相当于去掉了4然后继续对123%10就得到了3再除10去掉3依次类推不断地%10和/10操作直到1234的每一位都得到但是这里有个问题就是得到的数字顺序是倒着的但是最低位的数字是最容易得到的通过%10就能得到。print(n)如果n是1234那表示为print(1234)//打印1234的每一位其中1234中的4可以通过%10得到那么print1234就可以拆分为两步print1234/10//打印123的每一位printf1234%10//打印4完成上述2步那完成了1234每一位的打印那么print123又可以拆分为print123/10printf123%10依次类推print(1234)---------print(123) printf(4)---------print(12) printf(3)---------print(1) printf(2)---------printf(1)直到被打印的数字变成一位数的时候就不需要再拆分递归结束。代码如下3.递归和迭代递归是一种很好的编程技巧但是和很多技巧一样也是可能被误用的就像举例1一样看到推导的公式很容易就被写成递归的形式jie函数是可以产生正确的结果但是在递归函数调用的过程中涉及一些运行时的开销。在C语言中每一次函数调用都需要为本次函数调用在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次函数调用都会开辟属于自己的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。然后我们也可以使用循环迭代的方法实现方法一:由之前函数改装一下方法二上述代码是能够完成任务并且效率是比递归的方式更好的。但是我们看见的许多问题是以递归的形式进行解释的这只是因为它比非递归的形式更加清晰但是这些问题的迭代实现往往比递归实现效率更高。当一个问题非常复杂难以使用迭代的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。举例3求第n个斐波那契数我们也能举出更加极端的例子就像计算第n个斐波那契数是不适合递归求解的但是斐波那契数的问题通过是使用递归的形式描述的如下看到这公式我们很容易就写出代码当使用递归解决斐波那契数问题时且intput很大的时候会花费很多时间是我们很难接受的。因为在递归程序会不断地展开在展开的过程中我们很容易就能发现在递归的过程中会重复计算而且递归层次越深冗余计算就会越多。如下所示输出结果能看见在计算第40个斐波那契数的时候使用递归方式第3个斐波那契数就被重复计算了39088169次这些计算是非常冗余的所以斐波那契数的计算使用递归很麻烦我们就可以尝试使用循环迭代的方式。迭代的方式去实现代码一下子就出答案了。本文相关代码已经整理到 Giteehttps://gitee.com/ZhiWeiCoder/student_c如果这篇文章对你有一点帮助欢迎点赞、收藏、评论、关注也可以给我的代码仓库点个关注 ❤️C语言学习还在继续下一篇继续
