C语言(递归)

                        Hi~!这里是奋斗的小羊,很荣幸各位能阅读我的文章,诚请评论指点,关注+收藏,欢迎欢迎~~     

                        💥个人主页:小羊在奋斗

                        💥所属专栏:C语言   

        本系列文章为个人学习笔记,在这里撰写成文一为巩固知识,二为同样是初学者的学友展示一些我的学习过程及心得。文笔、排版拙劣,望见谅。

                               一、递归

                                        1、什么是递归

                                        2、递归的限制条件

                                        3、递归的举例

                                        4、递归与迭代

1、什么是递归

        递归是C语言学习绕不开的一个话题,那什么是递归呢?递归其实是一种解决问题的方法,在C语言中,递归就是函数自己调用自己。若一个复杂的问题,能层层分解为若干个相对简单且与原问题相似的子问题,则原问题可以采用递归算法求解,所以递归的思想就是把大事化小的过程。

        递归中的递是递推的意思,归是回归的意思。

        来看一个简单的递归示例:

        但是上述代码会陷入死递归,因为递归需要一个限制条件, 不然会一直向内存申请空间但不释放,导致栈溢出(Stack overflow)VS调试技巧中也提到过栈溢出,但这里也不细说,因为内容太多,后面会有专门的文章。

2、递归的限制条件

        递归在书写的时候,有2个必要的限制条件:

        (1)递归存在限制条件,也就是出口,当满足这个限制条件的时候,递归不再继续;

        (2)每次递归调用后越来越接近这个限制条件。

        这么说可能有些生硬,不过在看完了这篇文章后相信你会对这两句话有所体会。

3、递归的举例

        3.1求n的阶乘(不考虑溢出)

        我们知道,0和1的阶乘为1,n的阶乘是所有小于及等于n的正整数的积。

        比如:4!= 4*3*2*1,  3!= 3*2*1, 那么4!= 4*3!,即n!= n(n - 1)!。这样的思路就是把一个较大的问题,转换为一个与原问题相似,但规模较小的问题来解决。当n一直减到n = 1的时候,n的阶乘为1,这是我们本来就知道的。到这里,我们就得到了求n的阶乘的公式:

        函数实现如下:

#include <stdio.h>int fact(int x)
{if (0 == x || 1 == x){return 1;}else{return x * fact(x - 1);}
}int main()
{int n = 0;scanf("%d", &n);int m = fact(n);printf("%d\n", m);return 0;
}

         运行结果(这里不考虑n太大的情况,会溢出):

        图形演示:

         3.2输入一个整数顺序打印每一位

        我们拿到这个题目后,很容易想到把这个数的每一位单独拿出来再打印,但问题是,怎么拿到一个数的每一位呢?有一个熟知的方法就是通过模10(%10)和除10(/10)不断循环来取得一个数的每一位,但是这个办法取出来的是逆序的,我们这里需要的是顺序的,很明显我们常用的这个方法行不通。

        虽然这个方法行不通,但是它给了我们一个灵感,我们发现一个数的最低位是很容易得到的,因此我们可以这样想:如果想要按顺序打印1234的每一位,我们可以先打印123,再打印4;打印123之前先打印12,再打印3;打印12之前先打印1,再打印2。这样不就实现我们想要的效果了嘛。

        不难发现,上面解决问题的思路用递归很容易解决,既然有了思路,废话不多说,我们直接上代码演示:

#include <stdio.h>void print(int m)
{if (m > 9){print(m / 10);}printf("%d ", m % 10);
}int main()
{int n = 0;scanf("%d", &n);print(n);return 0;
}

        是不是看起来很简单,运行结果为:

        如果不太明白执行逻辑,不要慌,我直接上图细细演化每一步的执行过程:

4、递归与迭代

         递归是一种很好的编程技巧,但是和很多技巧一样,也是可能会被误用的。就像3.1一样,看到推导的公式,很容易就被写成递归的形式:

        Fact()函数是可以得出正确的结果,但是在函数递归的时候存在一些运行时的开销。

        在C语言中每一次函数调用,都需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值,这块空间被称为运行时栈帧,或者函数栈帧。只要函数不返回,函数对用的栈帧空间就一直被占用,所以如果函数调用中存在递归调用的话,每一次递归函数调用都会开辟属于自己的栈帧空间,直到函数递归不再继续,开始回归,才逐层释放栈帧空间。

        所以如果采用函数递归的方式完成代码,递归层次太深,就会浪费太多的栈帧空间,也可能引起溢出。

        为了避免这些问题,就得想其他的办法,通常就是用迭代的方法来代替递归。我们学过的循环就是一种迭代。比如上面的计算n的阶乘问题,我们也可以用循环的方法来解决:

        很明显,虽然递归的思想更容易理解,但是循环的方法更加简洁,也更加高效。

        事实上,我们看到的很多问题都是以递归的形式进行解释的,这只是因为它比非递归的形式更加清晰,但是这些问题的迭代实现往往比递归实现效率高。当一个问题非常复杂,难以使用迭代的方式实现时,递归实现的简洁性就弥补了它所带来时的运行时开销。

        例如:求第n个斐波那契数

        这个问题是不适合使用递归来求解的,但是斐波那契数的问题通常是用递归的形式来解释的:

        看到这个公式,我们很容易写出递归函数:

 

        看似我们用递归很容易的就解决了这个问题,但当我们输入较大的数时,程序运行的过程就会很费劲,比如我们输入50:

 

        可以看到程序运行了半天还没得出结果。为什么呢?其实,我们上面写出的代码在输入较大的数时,会有大量的重复计算,代码执行的效率非常低。这个时候我们就应该换个办法解决,比如循环。 

        那我们用循环具体该怎么实现呢?想要求第n个斐波那契数,无非就是这第n个数的前两个数相加,上面递归的方法其实是逆着计算的,在循环中我们可以顺着计算。假设第一个和第二个数分别为a和b,让a和b相加,值赋给c,再将b的值赋给a,将c的值赋给b,循环执行,直到n的值不再大于2,退出循环。

        当我们求第50个斐波那契数时,也会很快的得出答案(只是结果是错的,因为超过了整型的范围,影响不大):

 

        所以说,递归虽好,但不宜迷恋,要根据实际问题选择合适的解决方法。 

                                       点击跳转主页—> 💥个人主页小羊在奋斗

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3022318.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【练习3】

1.将二叉搜索树转为排序的双向链表 (好久没看数据结构&#xff0c;忘完了&#xff0c;学习大佬的代码&#xff09; class Solution { public:Node* prenullptr,*headnullptr; //pre为每次遍历时的前一个节点&#xff0c;head记录头节点Node* treeToDoublyList(Node* root) {if…

Web服务器和Tomcat

Web介绍 对于http协议操作进行封装、简化web程序开发 部署web项目&#xff0c;对外提供上网信息浏览 Tomcat介绍 一个轻量级的web服务器 也称为web容器 Tomcat的文件夹介绍 下载地址&#xff1a;Apache Tomcat - Apache Tomcat 9 Software Downloads 安装&#xff1a;直…

游戏理解入门:Rust+Bracket开发一个小游戏

1. Game loop 使用game loop可以使得游戏运行更加流畅和顺滑&#xff0c;它可以&#xff1a; 初始化窗口、图形和其他资源&#xff1b;每当屏幕刷新他都会运行(通常是每秒30,60 )&#xff1b;每次通过循环&#xff0c;他都会调用游戏的tick()函数。 大致的原理流程如下&…

【JUC】并发编程 Synchronized 锁升级原理

Synchronized如何实现同步/互斥的效果&#xff1f; monitorenter&#xff1a; 将锁对象对象头中Mark Word的前30bit替换成指向操作系统中与其关联的monitor对象&#xff0c;将锁记录位状态改为10 monitorexit&#xff1a; 将锁对象对象头中Mark Word进行重置&#xff0c;重新恢…

元器件的检测及万用表的使用

实验目的&#xff1a; 1. 了解万用表的结构和原理&#xff1b; 2. 识别常用电子元器件&#xff0c;学习使用万用表测量电阻、电感、电容和二极管的方法&#xff1b; 3. 学习使用万用表测量直流电压和直流电流的方法&#xff1b; 4. 理解万用表内阻对测量结果的影响&#xf…

Bert 实现情感分析任务

BERT Bert &#xff08;Bidirectional Encoder Representations from Transformers&#xff09;预训练模型是 Google 2018开源的自然语言模型&#xff0c;主要有以下特点。 像它名字一样&#xff0c;BERT最显著的特点是其能够为文本中的每个标记考虑双向上下文。与传统的基于…

【3dmax笔记】035: 车削修改器

一、车削修改器介绍 车削&#xff1a;图形通过绕轴旋转来创建三维效果。 开放的样条线&#xff0c;车削之后是面片。闭合的样条线&#xff0c;车削之后&#xff0c;是实体。 一、车削修改器实例 绘制高脚杯&#xff0c;首先在前视图绘制如下二维图形。 添加一个车削的修改器…

理解DPI:从数码到打印的深入分析

目录标题 1. DPI的定义2. DPI与图像质量2.1. 对于打印来说&#xff1a;2.2. 对于屏幕显示来说&#xff1a; 3. 如何计算DPI4. 调整DPI4.1. 提高DPI&#xff1a;4.2. 降低DPI&#xff1a; 5. DPI与图像文件大小的关系6. 实际应用中的DPI6.1. 专业打印&#xff1a;6.2. 屏幕设计&…

浏览器输入URL到页面展示的过程详解

重点面试题&#xff1a;当你的浏览器中地址栏输入地址并回车的一瞬间到页面能够展示回来&#xff0c;经历了什么&#xff1f; step 1、URL解析 URL&#xff1a;internet上的每一个网页都具有一个唯一的名称标识&#xff0c;通常称之为URL&#xff08;Uniform Resource Locator…

在国企分公司做信息宣传新闻投稿的经验分享

作为一名国企分公司的信息宣传工作者,我亲历了从传统投稿方式到数字化转型的全过程,这段经历既充满了挑战,也收获了成长。回首最初的日子,那些用邮箱投稿的时光,至今仍让我感慨万千。 初尝辛酸,邮箱投稿的艰难岁月 刚接手信息宣传工作时,我满腔热情,却很快被现实的冷水浇了个透…

springMVC入门学习

目录 1、 什么是springmvc 2、springmvc工作流程 3、 springmvc快速入门&#xff08;XML版本&#xff09; 4、加载自定义目录下的springmvc.xml配置文件 5、 解析器InternalResourceViewResolver 6、 映射器BeanNameUrlHandlerMapping 7、 适配器SimpleControllerHandle…

卡牌——蓝桥杯十三届2022国赛大学B组真题

样例输入 4 5 1 2 3 4 5 5 5 5样例输出 3样例说明 这 5 张空白牌中,拿2张写1,拿1张写2,这样每种牌的牌数就变为了3,3,3,4, 可以凑出 3套牌,剩下2张空白牌不能再帮助小明凑出一套。 评测用例规模与约定 对于30%的数据&#xff0c;保证n ⩽ \leqslant ⩽ 2000; 对于100%的数据…

低代码平台为什么被诟病?牛皮震天响,能力cover不住。

hello&#xff0c;我上有很多低代码平台&#xff0c;大多数停留在数据报表层面&#xff0c;所以在很多搞咖啡的眼里&#xff0c;低代码平台价值很低。 一、什么是低代码平台 低代码平台是一种开发工具或平台&#xff0c;旨在通过简化和加速应用程序开发过程&#xff0c;使开发…

代码随想录算法训练营第36期DAY14

DAY14&#xff08;周二&#xff09; 二叉树的递归遍历 144二叉树的前序遍历 过了。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullp…

算法学习(6)-最短路径

目录 Floyd-Warshall算法 Dijkstra算法 Bellman-Ford算法 Bellman-Ford的队列优化 最短路径算法对比分析 Floyd-Warshall算法 现在回到问题&#xff1a;如何求任意两点之间的最短路径呢&#xff1f; 通过之前的学习&#xff0c; 我们知道通过深度或广度优先搜索可以求出两…

CTF-reverse二维四向迷宫路径求解

二维四向迷宫是一个re中的常考点&#xff0c;说不上难&#xff0c;但也不简单&#xff0c;本篇记录了常规的二维四向迷宫解题套路以及帮助快速解题的脚本 可能你看我的教程会觉得十分繁琐&#xff0c;但实际只要你用了一次熟练之后&#xff0c;基本都是拿到迷宫就一题一分钟解决…

多模态EDA论文小记

论文地址 该论文主要改进点是&#xff1a;通过动态化局部搜索中每个集群大小&#xff0c;高斯和柯西分布共同产生个体。总的来说改进点不多&#xff0c;当然也可能是笔者还没发现。 局部搜索 划分集群 划分集群有两个策略分别是&#xff1a; 随机生成一个点作为中心点&…

【管理咨询宝藏96】企业数字化转型的中台战略培训方案

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏96】企业数字化转型的中台战略培训方案 【格式】PDF版本 【关键词】SRM采购、制造型企业转型、数字化转型 【核心观点】 - 数字化转型是指&…

C#winfrom三层架构实现简单课程管理系统管理系统,三层架构实现增删改查

1. 项目展示 1.1登录展示 1.2添加课程信息展示 1.3课程信息管理-查询-修改-删除 1.4修改登录密码 2.项目功能介绍&#xff08;图&#xff09; 3.数据库设计 3.1 教师表设计 3.2 课程分类表 3.3 课程信息表 4. 创建样式界面 winfrom 超详细UI创建过程 实现双色球选号器UI界面…

SharePoint 使用renderListDataAsStream方法查询list超过5000时的数据

问题&#xff1a; 当SharePoint List里的数据超过5000时&#xff0c;如果使用常用的rest api去获取数据&#xff0c;例如 await this.sp.web.lists.getByTitle(Document Library).rootFolder.files.select(*, listItemAllFields).expand(listItemAllFields).filter(listItemA…