http://blog.csdn.net/nxpzmj/article/details/9617159
总是听到大大们说递归递归的,自己写程序的时候却用不到递归。其中的原因,一个是害怕写递归,另一个就是不知道什么时候用递归。这篇文章就浅析一下,希望看完之后不再害怕递归,这就是本文最大的目的。
递归到底有什么意义?
在说怎么写递归之前必须要说一下它的意义,其实这就是为什么大多数人在看了许多递归的例子后还是不明所以的原因。可以肯定的是,递归是个十分强大的工具,有许多算法如果不用递归可能非常难写。很多地方介绍递归会用阶乘或者斐波那契数列作例子,这完全是在误导初学者。尽管用递归实现阶乘或者斐波那契数列是可以的,但是这是没有意义的。
先掉一下书袋,递归的定义是这样的:程序调用自身的编程技巧称为递归( recursion)。在函数调用的过程中是有一个叫函数调用栈的东西存在的。调用一个函数,首先要把原函数的局部变量等压入栈中,这是为了保护现场,保证调用函数完成后能够顺利返回继续运行下去。当调用函数返回时,又要将这些局部变量等从栈中弹出。在普通的函数调用中,一般调用深度最多不过十几层,但是来到了递归的世界情况就不一样了。先看一段随便从网上就能找到的阶乘程序
- double fab(int n)
- {
- if(n == 0 || n == 1){
- return 1;
- }else{
- return n*fab(n-1);
- }
- }
double fab(int n) { if(n == 0 || n == 1){ return 1; }else{ return n*fab(n-1); } }
如果n = 100,很显然这段程序需要递归地调用自身100次。这样调用深度至少就到了100。栈的大小是有限的,当n变的更大时,有朝一日总会使得栈溢出,从而程序崩溃。除此之外,每次函数调用的开销会导致程序变慢。所以说这段程序十分不好。那什么是好的递归,先给出一个结论,接着看下去自然会明白。结论是如果递归能够将问题的规模缩小,那就是好的递归。
怎样才算是规模缩小了呢。举个例子,比如要在一个有序数组中查找一个数,最简单直观的算法就是从头到尾遍历一遍数组,这样一定可以找到那个数。如果数组的大小是N,那么我们最坏情况下需要比较N次,所以这个算法的复杂度记为O(N)。有一个大名鼎鼎的算法叫二分法,它的表达也很简单,由于数组是有序的,那么找的时候就从数组的中间开始找,如果要找的数比中间的数大,那么接着查找数组的后半部分(如果是升序的话),以此类推,知道最后找到我们要找的数。稍微思考一下可以发现,如果数组的大小是N,那么最坏情况下我们需要比较logN次(计算机世界中log的底几乎总是2),所以这个算法的复杂度为O(logN)。当N变大后,logN << N,所以二分法会比直观的算法更快。而我们之后可以看到,二分法是可以用递归很简单的实现的(当然还有更好的方法,之后也会提到)。
简单的分析一下二分法为什么会快。可以发现二分法在每次比较之后都帮我们排除了一半的错误答案,接下去的一次只需要搜索剩下的一半,这就是说问题的规模缩小了一半。而在直观的算法中,每次比较后最多排除了一个错误的答案,问题的规模几乎没有缩小(仅仅减少了1)。这样的递归就稍微像样点了。
重新看阶乘的递归,每次递归后问题并没有本质上的减小(仅仅减小1),这和简单的循环没有区别,但循环没有函数调用的开销,也不会导致栈溢出。所以结论是如果仅仅用递归来达到循环的效果,那还是改用循环吧。
总结一下,递归的意义就在于将问题的规模缩小,并且缩小后问题并没有发生变化(二分法中,缩小后依然是从数组中寻找某一个数),这样就可以继续调用自身来完成接下来的任务。我们不用写很长的程序,就能得到一个十分优雅快速的实现。
怎么写递归程序
终于进入正题了。很多初学者都对递归心存畏惧,其实递归是符合人思考方式的。写递归程序是有套路的,总的来说递归程序有几条法则的。
用二分查找作为例子,先给出函数原型
- int binary_search(int* array, int start, int end, int num_wanted)
int binary_search(int* array, int start, int end, int num_wanted)
返回值是元素在数组中的位置,如果查找失败返回-1。
1. 基准情况
基准情况其实就是递归的终止条件。其实在实际中,这是十分容易确定的。例如在二分查找中,终止条件就是找到了我们想要的数或者搜索完了整个数组(查找失败)。
- if(end < start){
- return -1;
- }else if(num_wanted == array[middle]){
- return middle;
- }
if(end < start){ return -1; }else if(num_wanted == array[middle]){ return middle; }
2. 不断演进
演进的过程就是我们思考的过程,二分查找中,就是继续查找剩下的一半数组。
- if(num_wanted > array[middle]){
- index = binary_search(array, middle+1, end, num_wanted);
- }else{
- index = binary_search(array, start, middle-1, num_wanted);
- }
if(num_wanted > array[middle]){ index = binary_search(array, middle+1, end, num_wanted); }else{ index = binary_search(array, start, middle-1, num_wanted); }
当然这是比较简单的演进方式,其他的比如快速排序、树、堆的相关算法中会出现更复杂一点的演进过程(其实也复杂不到哪里去)。
3. 用人的思考方式设计
这条法则我认为是非常重要的,它不会出现在编码中,但却是理解递归的一条捷径。它的意思是说,在一般的编程实践中,我们通常需要用大脑模拟电脑执行每一条语句,从而确定编码的正确性,然而在递归编码中这是不需要的。递归编码的过程中,只需要知道前两条法则就够了。之后我们就会看到这条法则的如何工作的了。
4. 不要做重复的事情
在任何编码中,这都是不应该出现的事情,但是在递归中这更加可怕,可能由于一次多余的递归使得算法增加数级复杂度。之后也会看到相关的例子。
现在我们可以写出我们完整的二分法的程序了
- int binary_search(int* array, int start, int end, int num_wanted)
- {
- int middle = (end - start)/2 + start; // 1
- if(end < start){
- return -1;
- }else if(num_wanted == array[middle]){
- return middle;
- }
- int index;
- if(num_wanted > array[middle]){
- index = binary_search(array, middle+1, end, num_wanted); // 2
- }else{
- index = binary_search(array, start, middle-1, num_wanted); // 3
- }
- return index; // 4
- }
int binary_search(int* array, int start, int end, int num_wanted) { int middle = (end - start)/2 + start; // 1 if(end < start){ return -1; }else if(num_wanted == array[middle]){ return middle; } int index; if(num_wanted > array[middle]){ index = binary_search(array, middle+1, end, num_wanted); // 2 }else{ index = binary_search(array, start, middle-1, num_wanted); // 3 } return index; // 4 }
程序中除了1和4都已经在前两条法则的实现中了。1不必多说,4是一个比较关键的步骤,经常容易被忘记。这里就用到第3条法则,编写的时候只要认为2或者3一定会正确运行,并且立刻返回,不要考虑2和3内部是如何运行的,因为这就是你现在在编写的。这样4该如何处理就是显而易见的了,在这里只需要将找到的index返回就可以了。
第4条法则在这个例子里并没有出现,我们可以看一下斐波那契数列的递归实现
- long int fib(int n)
- {
- if(n <= 1){
- return 1;
- }else{
- return fib(n-1) + fib(n-2); // 1
- }
- }
long int fib(int n) { if(n <= 1){ return 1; }else{ return fib(n-1) + fib(n-2); // 1 } }
乍看之下,这段程序很精练,它也是一段正确的递归程序,有基准条件、不断推进。但是如果仔细分析一下它的复杂度可以发现,如果我们取n=N,那么每次fib调用会增加额外的2次fib调用(在1处),即fib的运行时间T(N) = T(N-1) + T(N-2),可以得到其复杂度是O(2^N),几乎是可见的复杂度最大的程序了(其中详细的计算各位有兴趣可以google一下,这里就不展开了^_^)。所以如果在一个递归程序中重复多次地调用自身,又不缩小问题的规模,通常不是个好主意。
PS. 大家可以比较一下二分法与斐波那契数列的递归实现的区别,尽管二分法也出现了2次调用自身,但是每次运行只有其中一个会被真正执行。
尾递归
到此其实你已经可以写出任何一个完整的递归程序了,虽然上面的例子比较简单,但是方法总是这样的。不过我们可以对递归程序再进一步分析。二分查找的递归算法中我们注意到在递归调用之后仅仅是返回了其返回值,这样的递归称作尾递归。尽管在编写的时候不必考虑递归的调用顺序,但真正运行的时候,递归的函数调用过程可以分为递和归两部分。在递归调用之前的部分称作递,调用之后的部分称作归。而尾递归在归的过程中实际上不做任何事情,对于这种情况可以很方便的将这个递归程序转化为非递归程序。
- int binary_search(int* array, int start, int end, int num_wanted)
- {
- int middle;
- search:
- middle = (end - start)/2 + start;
- if(end < start){
- return -1;
- }else if(num_wanted == array[middle]){
- return middle;
- }
- if(num_wanted > array[middle]){
- start = middle+1;
- end = end;
- goto search;
- //index = binary_search(array, middle+1, end, num_wanted);
- }else{
- start = start;
- end = middle-1;
- goto search;
- //index = binary_search(array, start, middle-1, num_wanted);
- }
- }
int binary_search(int* array, int start, int end, int num_wanted) { int middle; search: middle = (end - start)/2 + start; if(end < start){ return -1; }else if(num_wanted == array[middle]){ return middle; } if(num_wanted > array[middle]){ start = middle+1; end = end; goto search; //index = binary_search(array, middle+1, end, num_wanted); }else{ start = start; end = middle-1; goto search; //index = binary_search(array, start, middle-1, num_wanted); } }
上面就是去除递归后的二分查找的程序,我们只需要在程序开头处加上一个标号,在原本递归调用处修改参数的值并goto到标号就能完成这个工作。事实上,如果你写出了一个尾递归程序,在编译的时候编译器很可能就这样帮你优化了。当然这样的程序非常不符合我们的习惯,它实际上是将递归转化为了循环。循环还是应当使用while或者for实现,仔细地将上面这段程序改成while循环就成了这样。
- int binary_search(int* array, int start, int end, int num_wanted)
- {
- int middle = (end - start)/2 + start;
- while(end >= start && num_wanted != array[middle]){
- if(num_wanted > array[middle]){
- start = middle+1;
- }else{
- end = middle-1;
- }
- middle = (end - start)/2 + start;
- }
- if(end < start){
- return -1;
- }else{
- return middle;
- }
- }
int binary_search(int* array, int start, int end, int num_wanted) { int middle = (end - start)/2 + start; while(end >= start && num_wanted != array[middle]){ if(num_wanted > array[middle]){ start = middle+1; }else{ end = middle-1; } middle = (end - start)/2 + start; } if(end < start){ return -1; }else{ return middle; } }
这样就更加符合我们的习惯了,它比递归的版本速度略有提高,最重要的是不会导致栈溢出
相关推荐
项目包含完整前后端源码和数据库文件 环境说明: 开发语言:Java 框架:ssm,mybatis JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/idea Maven包:Maven3.3 服务器:tomcat7
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
1、嵌入式物联网单片机项目开发例程,简单、方便、好用,节省开发时间。 2、代码使用IAR软件开发,当前在CC2530上运行,如果是其他型号芯片,请自行移植。 3、软件下载时,请注意接上硬件,并确认烧录器连接正常。 4、有偿指导v:wulianjishu666; 5、如果接入其他传感器,请查看账号发布的其他资料。 6、单片机与模块的接线,在代码当中均有定义,请自行对照。 7、若硬件有差异,请根据自身情况调整代码,程序仅供参考学习。 8、代码有注释说明,请耐心阅读。 9、例程具有一定专业性,非专业人士请谨慎操作。
手语图像分类数据集【已标注,约2,500张数据】 分类个数【36】:0、1、a、b等【具体查看json文件】 划分了训练集、测试集。存放各自的同一类数据图片。如果想可视化数据集,可以运行资源中的show脚本。 CNN分类网络改进:https://blog.csdn.net/qq_44886601/category_12858320.html 【更多图像分类、图像分割(医学)、目标检测(yolo)的项目以及相应网络的改进,可以参考本人主页:https://blog.csdn.net/qq_44886601/category_12803200.html】
CNCAP 2024打分表
系统可以提供信息显示和相应服务,其管理智慧校园管理系统信息,查看智慧校园管理系统信息,管理智慧校园管理系统。 项目包含完整前后端源码和数据库文件 环境说明: 开发语言:Java JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/idea Maven包:Maven3.3 部署容器:tomcat7 小程序开发工具:hbuildx/微信开发者工具
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
影音互动科普网站功能描述 影音互动科普网站旨在通过多媒体形式(视频、音频、互动内容等)传播科学知识,提高公众的科学素养。该网站结合娱乐与教育,提供易于理解的科普内容,吸引不同年龄层次的用户参与和学习。以下是该网站的主要功能描述: 1. 用户注册与登录 用户注册:用户可以通过电子邮箱、手机号或社交账号(如微信、微博等)注册,提供基本信息并设置密码。 用户登录:支持通过注册的账号登录,保障个人信息的安全性,并提供自动登录功能。 2. 科普视频与音频库 视频内容:网站提供各类科普视频,包括短视频、纪录片、讲座、实验演示等,覆盖物理、化学、生物、地理、天文等多个领域。 音频内容:提供科普音频节目,如科普广播、播客、专题讲座等,便于用户在日常生活中进行学习。 视频分类:按科目、难度、年龄层、时长等维度对视频和音频进行分类,帮助用户更精准地找到感兴趣的内容。 字幕与多语言支持:提供字幕、翻译和多语种版本,帮助不同语言的用户学习。 3. 互动问答与讨论区 专家问答:用户可以向科普专家提问,专家提供详尽的解答,解决用户的科学疑惑。 社区讨论:用户可以在视频下方或专题页面中发表评论、提问或与其他用户
倪海厦讲义及笔记,易学数据测算
内容概要:本文档是《组合数学答案-网络流传版.pdf》的内容,主要包含了排列组合的基础知识以及一些经典的组合数学题目。这些题目涵盖了从排列数计算、二项式定理的应用到容斥原理的实际应用等方面。通过对这些题目的解析,帮助读者加深对组合数学概念和技巧的理解。 适用人群:适合初学者和有一定基础的学习者。 使用场景及目标:可以在学习组合数学课程时作为练习题参考,也可以在复习考试或准备竞赛时使用,目的是提高解决组合数学问题的能力。 其他说明:文档中的题目覆盖了组合数学的基本知识点,适合逐步深入学习。每个题目都有详细的解答步骤,有助于读者掌握解题思路和方法。
内容概要:本文是一篇完整的管理系统开发指南,详细介绍了功能要求、技术栈选择、数据库设计、用户界面搭建以及安全控制等方面的内容。功能要求包括用户管理、权限控制、数据管理、系统日志、通知与消息、统计分析和扩展模块。使用的技术栈涵盖了后端(Java、Python、C#等)和前端(React、Vue.js、Angular等)技术,以及数据库设计和安全控制措施。 适合人群:具备一定开发经验的软件工程师和技术管理人员。 使用场景及目标:适用于企业级管理系统开发项目,旨在构建一个高效、安全且易于扩展的系统。开发者可以参考本文档进行系统的设计和实现,确保系统满足业务需求。 其他说明:本文档提供了详细的步骤和最佳实践,帮助开发者更好地理解和应用管理系统开发的各种技术。通过结合实际案例和实践经验,本文档能够为开发者提供有价值的指导。
听器听力损伤程度分级表.docx
MATLAB代码:基于条件风险价值的合作型Stackerlberg博弈微网动态定价与优化调度 关键词:微网优化调度 条件风险价值 合作博弈 纳什谈判 参考文档:《A cooperative Stackelberg game based energy management considering price discrimination and risk assessment》完美复现 仿真平台:MATLAB yalmip+cplex+mosek 主要内容:代码主要做的是一个基于合作型Stackerlberg博弈的考虑差别定价和风险管理的微网动态定价与调度策略,提出了一个双层能源管理框架,实现多个微网间的P2P能源交易,上层为零商的动态定价模型,目标是社会福利最大化;下层是多个产消者的合作博弈模型,优化各产消者的能量管理策略。 同时,采用纳什谈判法对多个产消者的合作剩余进行公平分配,还考虑了运行风险,采用条件风险价值(CVaR)随机规划方法来描述零商的预期损失。 求解方面,双层模型被基于KKT条件转为单层模型,模型可以高效求解。 这段代码是一个基于合作型Stackelberg博弈的微网
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
20块钱买的【动漫网页设计】源码,免费分享出来啦,如果要积分那是系统自动涨的啦。 内容概要:本资源是一份动漫网页设计的源码,价格仅为20元,作者将其免费分享给大家。该源码包含了动漫元素的设计,包括背景、图标、按钮等,同时也提供了一些常见的网页布局和交互效果。通过该资源,可以学习到动漫网页设计的基本原理和技巧。 适用人群:本资源适用于对动漫网页设计感兴趣的人群,包括网页设计师、UI设计师、前端开发工程师等。同时,对于想要学习动漫网页设计的初学者也非常适用。 使用场景及目标:该资源可以用于学习和实践动漫网页设计的技巧和原理。通过学习该源码,可以了解到动漫网页设计的基本要素和设计思路,同时也可以借鉴其中的设计元素和交互效果,应用到自己的网页设计中。 其他说明:本资源是作者自己设计的,经过了多次修改和优化,具有一定的参考价值。同时,作者也将其价格设置的非常低,希望更多的人可以学习到动漫网页设计的技巧和方法。如果您对该资源有任何疑问或建议,欢迎在评论区留言,作者会尽快回复。。内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。
自考 本科 C++程序设计-课本 参考答案
每周质量安全排查报告.docx
YOLO算法-杂草检测项目数据集-3970张图像带标签-杂草.zip
内存搜索工具(易).rar
AI大模型研究相关报告