• 售前

  • 售后

热门帖子
入门百科

【C语言】函数递归(详解)

[复制链接]
弄乐诟 显示全部楼层 发表于 2022-1-13 13:46:24 |阅读模式 打印 上一主题 下一主题
文章目录



函数递归

程序调用自身的编程技巧称为递归 recursion)
函数自己调用自己就是递归
你也可以理解成是一种嵌套结构,但递归分为俩部分,第一是“递”,进入嵌套结构。第二是”归“,最终会一步一步返回。第一次接触递归都会很懵,慢慢理解这个过程就明白了。
什么是递归?

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的
一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
递归的主要思考方式在于:把大事化小
递归的俩个必要条件

代码引例1

接受一个整型值(无符号),按照顺序打印它的每一位。
例如:
输入:123,输出 1 2 3
参考代码:
  1. #include <stdio.h>
  2. void print(int n) {
  3. if(n>9)
  4. {
  5. print(n/10);
  6. }
  7. printf("%d ", n%10);
  8. }
  9. int main()
  10. {
  11. int num = 123;
  12. print(num);
  13. 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的阶乘
用循环的方法,代码如下:
[code]int main(){        int n = 0;        int ret = 1;        scanf("%d", &n);        //循环产生1~n的数字        int i = 0;        for (i = 1; i

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作