当前位置: 首页 > news >正文

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*14! = 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;elsereturn n*Fact(n-1);
}
测试:
#include <stdio.h>
int Fact(int n)
{if(n==0)return 1;elsereturn 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;elsereturn 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;elsereturn 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;elsereturn 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可以研究喔。

总结


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

相关文章:

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

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 函数递归 1、递归是什么&#xff1f; 1.1、递归的思想 1.2、递归的限制条件 2、递归举例 2.1、举例1&#xff1a;求n的阶乘 2.1.1、分析和代码实现 2.1.2、…...

etcd自动化安装配置教程

文章目录 前言一、简介1. 简介2. 特点3. 端口介绍 二、etcd安装教程&#xff08;单机版&#xff09;1. 复制脚本2. 增加执行权限3. 执行脚本4. 查看启动状态5. 卸载etcd 三、etcd安装教程&#xff08;集群版&#xff09;1. 复制脚本2. 增加执行权限3. 分发脚本4. 执行脚本5. 启…...

时间序列预测——GRU模型

时间序列预测——GRU模型 在深度学习领域&#xff0c;循环神经网络&#xff08;RNN&#xff09;是处理时间序列数据的一种常见选择。上期已介绍了LSTM的单步和多步预测。本文将深入介绍一种LSTM变体——门控循环单元&#xff08;GRU&#xff09;模型&#xff0c;包括其理论基础…...

通用CI/CD软件平台TeamCity全新发布v2023.11——增强Git托管平台的集成

TeamCity是一个通用的 CI/CD 软件平台&#xff0c;可以实现灵活的工作流、协作和开发做法。我们的解决方案将帮助在您的 DevOps 流程中成功实现持续集成、持续交付和持续部署。 TeamCity 2023.11正式版下载 TeamCity 2023.11 带来了矩阵构建和构建缓存等多项备受期待的功能&a…...

C语言:register类型变量

register—— 寄存器存储 register 是 C 语言中的一种存储类别&#xff08;Storage Class&#xff09;&#xff0c;它用于告诉编译器将变量存储在寄存器中。在 C 语言中&#xff0c;变量的存储位置可以是寄存器、堆栈或静态存储区&#xff0c;使用 register 存储类别可以帮助我…...

android 自定义下拉框

一、 简介&#xff1a; 原生Android 提供的spinner下拉框不怎么方便&#xff0c;样式有点丑。修改起来麻烦&#xff0c;于是就自己动手写了一下拉列表。 实现原理使用的是&#xff0c;popwindow弹框&#xff0c;可实现宽高自定义&#xff0c;下拉列表使用listview. 二、pop弹框…...

揭开时间序列的神秘面纱:特征工程的力量

目录 写在开头1. 什么是特征工程?1.1 特征工程的定义和基本概念1.2 特征工程在传统机器学习中的应用1.3 时间序列领域中特征工程的独特挑战和需求3. 时间序列数据的特征工程技术2.1 数据清洗和预处理2.1.1 缺失值处理2.1.2 异常值检测与处理2.2 时间特征的提取2.2.1 时间戳解析…...

vue3 源码解析(5)— patch 函数源码的实现

什么是 patch 在 vue 中 patch 函数的作用是在渲染的过程中&#xff0c;比较新旧节点的变化&#xff0c;通过打补丁的形式&#xff0c;进行新增、删除、移动或替换操作&#xff0c;此过程避免了大量的 dom 操作&#xff0c;提升了运行的性能。 patch 执行流程 patch 函数整体…...

蓝桥杯2024/1/28----十二届省赛题笔记

题目要求&#xff1a; 2、 竞赛板配置要求 2.1将 IAP15F2K61S2 单片机内部振荡器频率设定为 12MHz。 2.2键盘工作模式跳线 J5 配置为 KBD 键盘模式。 2.3扩展方式跳线 J13 配置为 IO 模式。 2.4 请注意 &#xff1a; 选手需严格按照以上要求配置竞赛板&#xff0c;编写和调…...

STM32+ESP8266 实现物联网设备节点

目录 一、硬件准备 二、编译环境 三、源代码地址 四、说明 五、测试方法 六、所有测试工具和文档 本项目使用stm32F103ZEesp8266实现一个物联网的通信节点&#xff0c;目前支持的协议有mqtt&#xff0c;tcp。后续会持续更新&#xff0c;增加JSON&#xff0c;传感器&#…...

免费的ChatGPT网站(7个)

还在为找免费的chatGPT网站或者应用而烦恼吗&#xff1f;博主归纳总结了7个国内非常好用&#xff0c;而且免费的chatGPT网站&#xff0c;AI语言大模型&#xff0c;我们都来接触一下吧。 免费&#xff01;免费&#xff01;免费&#xff01;...&#xff0c;建议收藏保存。 1&…...

Go语言基础之单元测试

1.go test工具 Go语言中的测试依赖go test命令。编写测试代码和编写普通的Go代码过程是类似的&#xff0c;并不需要学习新的语法、规则或工具。 go test命令是一个按照一定约定和组织的测试代码的驱动程序。在包目录内&#xff0c;所有以_test.go为后缀名的源代码文件都是go …...

C++ easyX小程序(介绍几个函数的使用)

本小程序通过代码和注释&#xff0c;介绍了easyX窗口及控制台窗口的设置方法&#xff1b;还介绍了easyX中关于颜色、线型、画圆、画方、显示文字以及鼠标消息处理等函数的使用方法。为便于理解&#xff0c;本程序同时使用控制台和easyX窗口&#xff0c;由控制台控制程序运行、由…...

配置nginx以成功代理websocket

配置nginx以成功代理websocket 在使用socket.io的时候遇到这样一个问题&#xff1a;websocket接收的消息的顺序错位了&#xff0c;然后看了一下浏览器的console的报错&#xff0c;提示连接到ws失败&#xff0c;然后在浏览器的开发者工具的网络中看了一下ws对应的消息里面报错&…...

代码随想录算法训练营第二十二天|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

文档讲解&#xff1a; BST&#xff0c;各种插入删除操作 235.二叉搜索树的最近公共祖先 思路&#xff1a;昨天练习了二叉树的搜索&#xff0c;今天这道题是二叉搜索树的搜索&#xff0c;其具有有序这个特点&#xff0c;其能决定我们每次搜索是进入该节点的左子树还是右子树&…...

collection、ofType、select的联合用法(Mybatis实现树状结构查询)

需求 得到树结构数据也可以用lambda表达式也行&#xff0c;也可以直接循环递归也行&#xff0c;本文采用的是直接在Mybatis层得到结果&#xff0c;各有各的优势。 代码 1、实体类 Data public class CourseChapterVO implements Serializable {private static final long s…...

FLUENT Meshing Watertight Geometry工作流入门 - 4 局部加密区域

本视频中学到的内容&#xff1a; 使用Watertight Geometry Workflow 的 Create Local Refinement Regions 任务来创建细化的网格区域 视频链接&#xff1a; FLUENT Meshing入门教程-4创建局部加密区域_哔哩哔哩_bilibili 可以通过使用 Watertight Geometry Workflow 的 Create…...

前端添加富文本/Web 富文本编辑器wangeditor

官网wangEditor 需要引入两个文件 <link href"https://unpkg.com/wangeditor/editorlatest/dist/css/style.css" rel"stylesheet"> <script src"https://unpkg.com/wangeditor/editorlatest/dist/index.js"></script> 前端…...

软件价值2-贪吃蛇游戏

贪吃蛇游戏虽然很多&#xff0c;不过它可以作为软件创作的开端&#xff0c;用python来实现&#xff0c;然后dist成windows系统可执行文件。 import pygame import sys import random# 初始化 pygame.init()# 游戏设置 width, height 640, 480 cell_size 20 snake_speed 15# …...

应用案例 | 基于三维机器视觉的汽车副车架在线测量解决方案

在汽车制造领域中&#xff0c;精确的测量是确保产品质量和生产效率的关键。随着科技的不断进步&#xff0c;测量技术也在不断精进。 副车架是汽车底盘的重要组成部分&#xff0c;负责支撑引擎&#xff0c;是车辆结构中至关重要的组成部分之一&#xff0c;其制造质量直接关系到汽…...

中兴光猫配置解密工具:3步解锁家庭网络自主权

中兴光猫配置解密工具&#xff1a;3步解锁家庭网络自主权 【免费下载链接】ZET-Optical-Network-Terminal-Decoder 项目地址: https://gitcode.com/gh_mirrors/ze/ZET-Optical-Network-Terminal-Decoder 你是否曾经因为无法修改光猫配置而感到束手无策&#xff1f;当网…...

eSearch一站式屏幕效率工具安装指南

eSearch一站式屏幕效率工具安装指南 【免费下载链接】eSearch 截屏 离线OCR 搜索翻译 以图搜图 贴图 录屏 万向滚动截屏 屏幕翻译 Screenshot Offline OCR Search Translate Search for picture Paste the picture on the screen Screen recorder Omnidirectional scrolling sc…...

手把手教你用Global Mapper搞定大范围遥感影像:从按县界裁剪到自动切片分发的完整流程

大范围遥感影像工程化处理实战&#xff1a;Global Mapper全流程解决方案 当面对覆盖全省的Sentinel-2影像时&#xff0c;大多数GIS工程师的第一反应可能是打开QGIS或ArcGIS Pro&#xff0c;配合GDAL命令行工具完成从裁剪到分发的全流程。但今天我要分享的是一条更高效的路径——…...

如何通过智能求职助手提升职位时间筛选效率?揭秘高效求职新方法

如何通过智能求职助手提升职位时间筛选效率&#xff1f;揭秘高效求职新方法 【免费下载链接】boss-show-time 展示boss直聘岗位的发布时间 项目地址: https://gitcode.com/GitHub_Trending/bo/boss-show-time 在当今竞争激烈的就业市场中&#xff0c;职位时间筛选已成为…...

对于多轮对话中的对话策略优化,OpenClaw 的在线强化学习更新频率?

关于OpenClaw在多轮对话中对话策略的在线强化学习更新频率&#xff0c;其实并没有一个公开的、固定的官方数字。这倒不是因为它是什么秘密&#xff0c;而是因为这类系统的更新机制往往不是按“每隔几秒一次”这样刻板的方式来运作的。它更像是一个动态调整的过程&#xff0c;取…...

游戏多开防封号?聊聊用天翼云低成本搭建SK5代理池的真实体验与避坑心得

游戏多开防封号实战&#xff1a;天翼云SK5代理池搭建全记录与深度优化指南 作为一名资深游戏多开玩家&#xff0c;我曾在《魔兽世界》怀旧服同时运营8个采集账号&#xff0c;结果三天内全军覆没——官方封号邮件里赫然写着"同一IP下异常多账号操作"。这次惨痛经历让…...

Qwen3-14B企业知识图谱构建:从私有文档抽取实体关系实践

Qwen3-14B企业知识图谱构建&#xff1a;从私有文档抽取实体关系实践 1. 企业知识图谱构建概述 在当今企业数字化转型浪潮中&#xff0c;知识图谱作为结构化知识表示的重要方式&#xff0c;正成为企业知识管理的核心基础设施。传统知识图谱构建需要大量人工标注和规则设计&…...

别再只用L1/L2了!用PyTorch实战图像修复的5种高阶损失函数(含VGG19感知损失代码)

超越L1/L2&#xff1a;PyTorch图像修复中5种高阶损失函数的工程实践 当你在深夜调试一个图像超分辨率模型时&#xff0c;发现生成的图片虽然PSNR值很高&#xff0c;但总感觉缺少那种"真实感"——边缘不够锐利&#xff0c;纹理略显模糊。这时候&#xff0c;L1/L2损失函…...

Win11系统升级后如何快速恢复MySQL数据库

1. Win11升级后MySQL恢复的常见场景 最近帮朋友处理了一个典型问题&#xff1a;他的Win11系统升级后&#xff0c;原本运行正常的MySQL服务突然无法启动&#xff0c;项目数据库全部"消失"。这种情况其实很常见——系统升级或重装时&#xff0c;注册表信息、环境变量和…...

Phi-3-mini-4k-instruct-gguf实战教程:开箱即用的轻量中文问答部署指南

Phi-3-mini-4k-instruct-gguf实战教程&#xff1a;开箱即用的轻量中文问答部署指南 1. 认识Phi-3-mini-4k-instruct-gguf Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本。这个模型特别适合处理中文问答、文本改写、摘要整理以及简短创作等任务。…...