C语言第十四弹---函数递归

 

57abfd7f66fb47249f03bc2e7690ea5e.jpeg

  ✨个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】

函数递归

1、递归是什么?

1.1、递归的思想:

1.2、递归的限制条件

2、递归举例

2.1、举例1:求n的阶乘

2.1.1、分析和代码实现

2.1.2、画图推演

2.2、举例2:顺序打印⼀个整数的每⼀位

2.2.1、分析和代码实现

2.2.2、画图推演

3、递归与迭代

3.1、举例3:求第n个斐波那契数

总结


 

1、递归是什么?

 
递归是学习C语言函数绕不开的⼀个话题,那什么是递归呢?
递归其实是⼀种解决问题的⽅法,在C语言中,递归就是函数自己调⽤自己。
写⼀个史上最简单的C语⾔递归代码:
#include <stdio.h>
int main()
{
 printf("hehe\n");
 main();//main函数中又调用了main函数
 return 0;
}
上述就是⼀个简单的递归程序,只不过上面的递归只是为了演示递归的基本形式,不是为了解决问
题,代码最终也会陷入死递归,导致栈溢出(Stack overflow)。
e4489bfd0ff342de96506634badf32a6.png
 

1.1、递归的思想

 
把⼀个大型复杂问题层层转化为⼀个与原问题相似,但规模较小的子问题来求解;直到子问题不能再被拆分,递归就结束了。所以递归的思考方式就是把 大事化小的过程。
递归中的 递就是递推的意思, 归就是回归的意思,接下来慢慢来体会。
 

1.2、递归的限制条件

 
递归在书写的时候,有2个必要条件:
• 递归存在限制条件,当满足这个限制条件的时候,递归便不再继续。
• 每次递归调用之后越来越接近这个限制条件。
 
在下面的例子中,我们逐步体会这2个限制条件。
 

2、递归举例

 

2.1、举例1:求n的阶乘

 
⼀个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。
自然数n的阶乘写作n!。
题目:计算n的阶乘(不考虑溢出),n的阶乘就是1~n的数字累积相乘。
 

2.1.1、分析和代码实现

 
我们知道n的阶乘的公式: n! =   n ∗ ( n − 1)!
 
举例:
 5! = 5*4*3*2*1
 4! = 4*3*2*1
 所以:5! = 5*4!
这样的思路就是把⼀个较大的问题,转换为⼀个与原问题相似,但规模较小的问题来求解的。
当 n==0 的时候,n的阶乘是1,其余n的阶乘都是可以通过公式计算。
n的阶乘的递归公式如下:
5f0057895b0441f6a89811e88f260978.png
那我们就可以写出函数Fact求n的阶乘,假设Fact(n)就是求n的阶乘,那么Fact(n-1)就是求n-1的阶
乘,函数如下:
int Fact(int n)
{
 if(n==0)
 return 1;
 else
 return n*Fact(n-1);
}
测试:
#include <stdio.h>
int Fact(int n)
{
 if(n==0)
 return 1;
 else
 return n*Fact(n-1);
}
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fact(n);
 printf("%d\n", ret);
 return 0;
}
运行结果(这里不考虑n太⼤的情况,n太大存在溢出):
6673ed9bed754a788eb4eafd943c08af.png
 

2.1.2、画图推演

 
35f62bda36a14afb8b1fd58f44427529.png
建议初次学习递归时画上述的递归展开图,更容易理解是如何进行递归的。
 

2.2、举例2:顺序打印⼀个整数的每⼀位

 
输⼊⼀个整数m,打印这个按照顺序打印整数的每⼀位。
比如:
输入:1234 输出:1 2 3 4
输入:520 输出:5 2 0
 

2.2.1、分析和代码实现

 
这个题目,放在我们面前,首先想到的是,怎么得到这个数的每⼀位呢?
 
如果n是⼀位数,n的每⼀位就是n自己;
n是超过1位数的话,就得拆分每⼀位。
1234%10就能得到4,然后1234/10得到123,这就相当于去掉了4
然后继续对123%10,就得到了3,再除10去掉3,以此类推
不断的 %10 和 /10 操作,直到1234的每⼀位都得到;
 
但是这里有个问题就是得到的数字顺序是倒着的。
但是我们有了灵感,我们发现其实⼀个数字的最低位是最容易得到的,通过%10就能得到。
 
那我们假设想写⼀个函数Print来打印n的每⼀位,如下表示:
Print(n)
如果n是1234,那表示为
Print(1234) //打印1234的每⼀位
其中1234中的4可以通过%10得到,那么
Print(1234)就可以拆分为两步:
1. Print(1234/10) //打印123的每⼀位
2. printf(1234%10) //打印4

完成上述2步,那就完成了1234每⼀位的打印
那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10)

 

以此类推下去,就有
Print(1234)
==>Print(123) + printf(4)
==>Print(12) + printf(3)
==>Print(1) + printf(2)
==>printf(1)

 

直到被打印的数字变成⼀位数的时候,就不需要再拆分,递归结束。
 

那么代码完成也就比较清楚:

void Print(int n)
{
if(n>9)
{
Print(n/10);
}
printf("%d ", n%10);
}
int main()
{
int m = 0;
scanf("%d", &m);
Print(m);
return 0;
}
 
输入和输出结果:
99b075f540b64e95aeb967bfb99a871e.png
 
 
在这个解题的过程中,我们就是使用了 大事化小的思路
把Print(1234) 打印1234每⼀位,拆解为首先Print(123)打印123的每⼀位,再打印得到的4
把Print(123) 打印123每⼀位,拆解为首先Print(12)打印12的每⼀位,再打印得到的3
直到Print打印的是⼀位数,直接打印就行。
 

2.2.2、画图推演

 
以1234每⼀位的打印来推演⼀下
f1819a4df7ca45dd939f15f5b2976b69.png
 

3、递归与迭代

 
递归是⼀种很好的编程技巧,但是很多技巧⼀样,也是可能被误用的,就像举例1⼀样,看到推导的公式,很容易就被写成递归的形式:
bda704b53b9b45e681250aebd6269d8f.png
int Fact(int n)
{
 if(n==0)
 return 1;
 else
 return n*Fact(n-1);
}
Fact函数是可以产生正确的结果,但是在递归函数调用的过程中涉及⼀些运行时的开销。
在C语⾔中每⼀次函数调用,都要需要为本次函数调用在栈区申请⼀块内存空间来保存函数调用期间的各种局部变量的值,这块空间被称为运行时堆栈,或者函数栈帧。
函数不返回,函数对应的栈帧空间就⼀直占用,所以如果函数调用中存在递归调用的话,每⼀次递归函数调用都会开辟属于自己的栈帧空间,直到函数递归不再继续,开始回归,才逐层释放栈帧空间。
所以如果采用函数递归的方式完成代码,递归层次太深,就会浪费太多的栈帧空间,也可能引起栈溢出(stack overflow)的问题。
 
注: 关于函数栈帧的详细内容,后序章节会详细讲解。
 
所以如果不想使用递归就得想其他的办法,通常就是迭代的方式(通常就是循环的方式)。
比如:计算n的阶乘,也是可以产⽣1~n的数字累计乘在⼀起的。
 
int Fact(int n)
{
 int i = 0;
 int ret = 1;
 for(i=1; i<=n; i++)
 {
 ret *= i;
 }
 return ret;
}
上述代码是能够完成任务,并且效率是比递归的方式更好的。(在数据结构初阶时间和空间复杂度有详细讲解效率问题)
 
事实上,我们看到的许多问题是以递归的形式进行解释的,这只是因为它比非递归的形式更加清晰, 但是这些问题的迭代实现往往比递归实现效率更高。
当⼀个问题非常复杂,难以使用迭代的方式实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销。
 

3.1、举例3:求第n个斐波那契数

 
我们也能举出更加极端的例⼦,就像计算第n个斐波那契数,是不适合使用递归求解的,但是斐波那契数的问题通过是使⽤递归的形式描述的,如下:
 
 
看到这公式,很容易诱导我们将代码写成递归的形式,如下所示:
f6c1e3c0aa484d43940150da2dac42ae.png
int Fib(int n)
{
 if(n<=2)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
测试代码:
#include <stdio.h>
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fib(n);
 printf("%d\n", ret); 
 return 0;
}
当我们n输入为50的时候,需要很长时间才能算出结果,这个计算所花费的时间,是我们很难接受的, 这也说明递归的写法是非常低效的,那是为什么呢?
e857efe6578b493a97ac0a3cc435d196.png
 
其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计
算,而且递归层次越深,冗余计算就会越多。我们可以做个测试:
 
#include <stdio.h>
int count = 0;
int Fib(int n)
{
 if(n == 3)
 count++;//统计第3个斐波那契数被计算的次数
 if(n<=2)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fib(n);
 printf("%d\n", ret); 
 printf("\ncount = %d\n", count);
 return 0;
}
输出结果:
6da1234c8ca9477eb40f1e73cddd31da.png
 
 
这里我们看到了,在计算第 40个斐波那契数的时候,使用递归方式,第3个斐波那契数就被重复计算了 39088169次,这些计算是非常冗余的。所以斐波那契数的计算,使用递归是非常不明智的,我们就得想迭代的方式解决。
我们知道斐波那契数的前2个数都1,然后前2个数相加就是第3个数,那么我们从前往后,从小到大计算就行了。
这样就有下面的代码:
int Fib(int n)
{
 int a = 1;
 int b = 1;
 int c = 1;
 while(n>2)
 {
 c = a+b;
 a = b;
 b = c;
 n--;
 }
 return c;
}
迭代的方式去实现这个代码,效率就要高出很多了。
有时候,递归虽好,但是也会引入⼀些问题,所以我们⼀定不要迷恋递归,适可而止就好。
 
 
拓展学习:
• 青蛙跳台阶问题
• 汉诺塔问题
以上2个问题都可以使用递归很好的解决,有兴趣uu可以研究喔。
 

总结


本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用vue脚手架构建项目

一、前言 * 创建好vue-cli的环境&#xff0c;下载好vue包依赖* 本文使用环境&#xff1a;vue/cli 5.0.8二、步骤 创建vueTest文件夹&#xff0c;管理员身份运行cmd , 进入到vueTest文件夹 执行命令vue create 你的项目名 &#xff0c;这里我定义的项目名为: my-project 基于…

Django实例_后台管理及分页器

原理步骤参考: Django开发_14_后台管理及分页器-CSDN博客 一、创建Django项目 二、创建page_app python manage.py startapp page_app三、修改settings.py文件 (一)添加app (二)设置每页显示数据个数 (三)设置中文显示 四、总路由添加子路由路径 from django.contrib impo…

中国的茶文化:历史、传统与生活

中国的茶文化&#xff1a;历史、传统与生活 一、引言 茶&#xff0c;这一神奇而古老的饮品&#xff0c;与中国的历史、文化和生活方式紧密相连。中国的茶文化&#xff0c;源远流长&#xff0c;博大精深&#xff0c;是中华文明的重要组成部分。它不仅是一种饮料&#xff0c;更是…

Hutool导入导出用法

整理了下Hutool导入导出的简单使用。 导入maven或jar包&#xff08;注意这里导入的poi只是为了优化样式&#xff09; <!-- https://mvnrepository.com/artifact/cn.hutool/hutool-all --> <dependency><groupId>cn.hutool</groupId><artifactId&g…

用低版本python的时候pip无法联网

如图所示&#xff0c;我用较低版本pip&#xff08;3.7&#xff0c;3.8&#xff09;的时候pip无法使用代理联网 看报错是代理问题&#xff0c; 那么直接在pip的时候直接加上自己科学上网的代理就ok了 当然也可以换源解决&#xff0c;这个网上教程挺多的就自己搜搜好了hhh

在 Linux 中挂载新硬盘动态使用

目录 一&#xff1a;添加硬盘并且格式化 二&#xff1a;创建逻辑卷 三&#xff1a;挂载卷到目录 在 Linux 中挂载新硬盘并进行格式化的操作可以按照以下步骤进行&#xff1a; 一&#xff1a;添加硬盘并且格式化 查看现有分区状态和服务器安装的硬盘状态&#xff1a; df -…

SpringBoot---创建项目

介绍 此项目SpringBoot使用的是2.6.1版本&#xff0c;由于这个项目使用的是maven聚合方式创建的&#xff0c;所以第二步是我在聚合方式下需要添加的依赖&#xff0c;完整的pom.xml内容放到了最下面。 第一步&#xff1a;创建Maven项目 这个里什么也不勾选&#xff0c;直接点…

Java面向对象详解

面向对象和面向过程的区别&#xff1a; 面向对象和面向过程都是对软件分析、设计和开发的一种思想&#xff0c;它指导着人们以不同的方式去分析、设计和开发软件。C语言是一种典型的面向过程语言&#xff0c;Java是一种典型的面向对象语言。 面向过程适合简单、不需要协作的事务…

时序预测 | PyTorch基于改进Informer模型的时间序列预测(锂电池SOC估计)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 时序预测 | PyTorch基于改进Informer模型的时间序列预测&#xff0c;锂电池SOC估计 时间序列预测&#xff1a;informer改进模型[new][new][new]&#xff08;Fourier-Mixed Window Informer 采用傅里叶混合窗口注意力机…

用React给XXL-JOB开发一个新皮肤(四):实现用户管理模块

目录 一. 简述二. 模块规划 2.1. 页面规划2.2. 模型实体定义 三. 模块实现 3.1. 用户分页搜索3.2. Modal 配置3.3. 创建用户表单3.4. 修改用户表单3.5. 删除 四. 结束语 一. 简述 上一篇文章我们实现登录页面和管理页面的 Layout 骨架&#xff0c;并对接登录和登出接口。这篇…

cpu到达100%问题排查

0、背景 首先定位到mysql 的cpu使用率较高 原因是任务域的作业实例补偿定时任务相关sql查询问题&#xff0c;该sql 2min执行一次&#xff0c;一次查询两次&#xff0c;导致cpu飙升&#xff0c;可考虑优化sql&#xff0c;添加以下索引 ALTER TABLE scheduler.tbl_simba_os_sc…

Linux编辑器之vim的使用

文章目录 一、vim简介二、vim的基本概念三、vim的基本操作四、vim正常模式命令集移动光标删除文字复制替换撤销上一次操作更改跳至指定的行vim末行模式命令集列出行号跳到文件中的某一行查找字符保存文件离开vim 五、进阶vim玩法打开文件批量注释代码执行shell命令指定注释窗口…

Excel中将16进制数转化成10进制(有/无符号)

Excel中将16进制数转化成10进制&#xff08;有/无符号&#xff09; Excel或者matlab中常用XXX2XXX进行不同进制的转换 16进制转10进制&#xff08;无符号数&#xff09;&#xff1a;HEX2DEC 16进制转10进制&#xff08;有符号数&#xff09;&#xff1a; FA46为例&#xff0c…

AWS 专题学习 P16 (Disaster Recovery Migrations)

文章目录 专题总览Disaster Recovery Overview1. RPO and RTO2. Disaster Recovery Strategies3. Backup & Restore&#xff08;High RPO&#xff09;4. Disaster Recovery – Pilot Light (试点灯)5. Warm Standby&#xff08;暖待命&#xff09;6. Multi Site / Hot Site…

Linux进程间通信(IPC)机制之一:共享内存

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;Nonsense—Sabrina Carpenter 0:50━━━━━━️&#x1f49f;──────── 2:43 &#x1f504; ◀️ ⏸ ▶️ …

2024年【危险化学品经营单位安全管理人员】考试内容及危险化学品经营单位安全管理人员模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【危险化学品经营单位安全管理人员】考试内容及危险化学品经营单位安全管理人员模拟考试&#xff0c;包含危险化学品经营单位安全管理人员考试内容答案和解析及危险化学品经营单位安全管理人员模拟考试练习。安…

如何提高思维能力,洞悉事物本质?(一)

什么是思维模型&#xff08;Mental Model&#xff09;&#xff1f; 你可能会在不少文章、培训课里面&#xff0c;看到这个名字。它们往往会用复杂的词汇和概念&#xff0c;通常还会扯上一些名人&#xff0c;把它包装得高深莫测。 但实际上&#xff0c;思维模型究竟是什么呢&…

照明灯具哪个品牌好知乎?质量最好的护眼台灯排行榜

台灯是家中必不可少的用品之一&#xff0c;它不仅能够提供基础的照明功能&#xff0c;还能营造出不一样的风格和氛围&#xff0c;影响人们的心情和生活品质。而一台好的护眼台灯还能够呵护我们的眼睛&#xff0c;保护好视力健康。想拥有一台使用体验感又好&#xff0c;寿命又长…

故障诊断 | 一文解决,SVM支持向量机的故障诊断(Matlab)

效果一览 文章概述 故障诊断 | 一文解决,SVM支持向量机的故障诊断(Matlab) 支持向量机(Support Vector Machine,SVM)是一种常用的监督学习算法,用于分类和回归分析。SVM的主要目标是找到一个最优的超平面(或者在非线性情况下是一个最优的超曲面),将不同类别的样本分开…

Vue3中ElementPlus组件二次封装,实现原组件属性、插槽、事件监听、方法的透传

本文以el-input组件为例&#xff0c;其它组件类似用法。 一、解决数据绑定问题 封装组件的第一步&#xff0c;要解决的就是数据绑定的问题&#xff0c;由于prop数据流是单向传递的&#xff0c;数据只能从父流向子&#xff0c;子想改父只能通过提交emit事件通知父修改。 父&a…