2021-04-25

递归******## 一,什么是递归### 1.递归的详细定义程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。### 2.递归的简单理解所谓递归从字面意思上就可以看出来,递归可以拆分成传递和回调两个过程,递归是一个不断调用自身,并返回结果的过称,当然递归也不可能无限制的调用返回,需要条件来控制递归,并且需要有程序实现不断地向递归的条件靠拢,否则就算有递归的条件,也只是不断地在原地踏步,这也就指出了递归的两个条件### 3.递归的基本思想递归的基本思想,是把规模较大的一个问题,分解成规模较小的多个处理方法相同的子问题去解决,而每一个子问题又可以继续拆分成多个更小的处理方法相同的子问题。 最重要的一点就是假设所有的子问题已经解决了,现在要基于已经解决的子问题来解决当前问题;递归就是一个逐层深入的过程,打个比方就好比,就相当于与我们编程的时候遇到一个特别难的问题,我自己不能解决,我们需要求助他人,这个难题很多人都解决不了,最后传到了编程界最牛的人手里被解决了(这就好比递归的限制条件,如果大牛都解决不了那不崩了),当大牛解决问题后答案被返还回我,这样这个问题就被我解决了,这就是递归。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SYqqCF1b-1619355275386)(E:\图片\src=http___images0.cnblogs.com_blog2015_682679_201503_292059315203552.png&refer=http___images0.cnblogs.jpg)]### 4.递归存在的两个必要条件- 存在限制条件,当满足这个限制条件的时候,递归便不再继续。- 每次递归调用之后越来越接近这个限制条件。 ## 二, 如何使用递归以及使用过程中的一些问题### 1.举例练习递归#### 例1 接受一个整形值(无符号),按顺时针打印它的每一位。例如:输入:1234,输出1 2 3 4.c#include<stdio.h>void print(int n){ if (n > 9) { print(n / 10); } printf("%d\n", n % 10);}int main(){ int num = 1234; print(num); return 0;}代码分析:这是一个很简单的代码,目的是输入1234,输出1 2 3 4 首先进入函数print,当n大于9时执行程序,否则执行下一句程序,当输入1234时,进入判断条件,在一次调用print函数,并将n/10,变成123,在一次进入print函数,执行判断语句,变成12,再重复上述过程直到n = 1,时,再一次进入print程序时不满足条件,执行下面条件输出1,然后返回上一级输出2,依次输出3,4,具体过程如图所示例1#### 例2 编写函数不允许创建临时变量,求字符串长度。首先,我们先用一个创建临时变量代码实现求字符串长度的代码,来进一步加深不用创建临时变量求字符串长度的方法c#include<stdio.h>int mn_strlen(char* p){ int count = 0; while (*p != '\0') { p++;//将指针后移一位 count++;//如果不是\0就是自增1 } return count;}int main(){ char arr[] = "bit"; printf("%d\n", mn_strlen(arr)); return 0;}代码分析:改代码模拟实现了strlen的功能,灵活的运用了指针,strlen函数的原理是:找到字符串结束标志\0, 并统计\0前所有字符的个数。下面我们来看看不用创建临时变量,来实现求字符串长度的方法。c#include<stdio.h>int MN_strlen(char* p){ if (*p == '\0') { return 0; } else { return 1 + MN_strlen(p + 1); }}int main(){ char arr[] = "bit"; printf("%d\n", MN_strlen(arr)); return 0;}代码分析:原理和上述原理相同,具体过程如图。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0Y7UCQbZ-1619355275388)(E:\图片\QQ截图20210418164355.png)]#### 例3 :求n的阶乘。(不考虑溢出)c#include<stdio.h>int Fac(int n){ if (n <= 1) { return 1; } else { return n * Fac(n - 1); }}int main(){ int input; printf("请输入一个数:\n"); scanf("%d", &input); printf("%d 的阶乘为 %d\n", input, Fac(input)); return 0;}代码分析: 当n小于等于1时n的阶乘为1,当n大于1时n的阶乘为n乘n-1的阶乘,以此类推n-1的阶乘等于n-1乘n-2的阶乘,直到n等于1为止,返回n等于1的阶乘,从而返回n等于二的阶乘,直到返回n等于n-1的阶乘,进而求出n阶乘。#### 例4 :求第n个斐波那契数。 (不考虑溢出)c#include<stdio.h>int fib(int n){ if (n <= 2) { return 1; } else { return fib(n - 1) + fib(n - 2); }}int main(){ int input; printf("请输入一个数:\n"); scanf("%d", &input); printf("第n个斐波那契数为%d\n", fib(input)); return 0;}在运算例3,例4时可能会发生一些问题- 当我们运行fib这个函数时,如果我们想要求第50个或者更大的数时我们会发现,我们通常会需要更长的时间。- 当我们运行Fac这个函数时,如果我们想要求1000的阶乘或者更大的数时我们会发现程序崩溃了**为什么呢?**我们发现fib在执行过程中有很多计算步骤都是重复的,下面我们将代码修改一下:cint count = 0;int fib(int n){ if (n == 3) { count++; } if (n <= 2) { return 1; } else { return fib(n - 1) + fib(n - 2); }}最后我们可看以看到输出的count是一个很大的数,这说明了这种算法在计算上有很多重复,这也是递归算法的缺点,递归算法的优点在于代码简洁,易于理解,但缺点在于时间和空间消耗较大,并且有可能发生栈溢出现象,递归中又有很多计算都是重复的,递归的本质时把一个问题分解成两个或多个小 问题,多个小问题存在重叠的部分,即存在重复计算,正如上面斐波那契数列的递归实现。在调试fib函数的时候,如果你的参数比较大,那就会报错:stack overflow (栈溢出)这样的信息,系统分配给栈的空间是有限的,如果出现死了死循环或者死递归,这样有可能导致一直开辟空间,最终导致栈空间耗尽的情况,这种现象我们成为栈溢出。那么如何解决这种问题呢?## 三, 如何解决栈溢出问题,并对程序进行优化。有以下两种方法:第一种就是: ### 1. 将递归改为尾递归的形式: 那么什么是尾递归呢,以下内容是对尾递归的书面解释:如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码,下面我们通过一幅图片来解释一下什么时尾递归。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZjD7VMCc-1619355275388)(E:\图片\10688072-6f90a34dcf7ee330.webp)]当编译器测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高,实际上尾递归并没有像普通递归那样每次都会在栈上开辟新的空间,而是选则去覆盖之前的空间,这样下来最终相当于尾递归最后只开辟了一次栈空间,只返回了一次,这样大大减少了栈空间的开辟,提高了空间的利用率,也减少了时间的浪费。下面我们用尾递归来重新改写一下n的阶乘。c#include<stdio.h>int fab(int n, int a)//每次调用函数时都将a初始化为1{ if (n < 0) { return 0; } if (n == 0) { return 1; } if (n == 1) { return a;//调用尾递归最后将a的值返回 } if (n > 1) { return fab(n - 1, n * a);//开始调用递归直到n=1为止 }}int main(){ int input; printf("请输入一个数: >\n"); scanf("%d", &input); int ret = fab(input, 1); printf("%d\n", ret); return 0;}这样通过图片和实例,理解起来应该会很容易第二种就是:### 2. 将递归改为非递归的形式:将递归改为非递归的形式:又细分为下面两种方法, 而这里只总结第一种方法。1.迭代的算法:所谓迭代简单的理解理解就是重复的反馈活动,就是重复执行同一算法,并将上一次运算的结果,作为下一次运算的初始值,直到循环满足条件,停止并返回相应的值。迭代相比较递归具有的优点是,代码运行效率高,时间和空间上没有多余的开销,相比较于递归的不足之处在于代码没有递归简洁,通俗易懂。下面我们用迭代来写一下n的阶乘和第n个斐波拉契数。c//迭代法求n的阶乘int fac(int n){ int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret;}int main(){ int input; printf("请输入一个数:\n"); scanf("%d", &input); printf("%d 的阶乘为 %d\n", input, fac(input)); return 0;}//迭代法求第n个斐波那契数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;}int main(){ int input; printf("请输入一个数:\n"); scanf("%d", &input); printf("第n个斐波那契数为%d\n", fib(input)); return 0;}使用这种方法可以很好的解决递归的一些缺点,并且很好的解决了栈溢出的问题。2.借助堆栈模拟递归的执行过程。这种方法就不具体介绍了,因为我还没有学数据结构自己的理解也并不是很好,后期学了数据结构,就在写一篇关于这种方法的博客吧。## 四, 那么递归和迭代我们应该如何选择呢 1.许多问题是以递归的形式解决的,这是因为他比非递归的形式更为清晰。 2.但是这些问题的迭代形式实现往往比递归实现效率更高,虽然代码可读性稍微差一些。 3.当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以弥补它所带来的运行时的开销。## 五,函数递归的几个经典题目- 汉诺塔问题- 青蛙跳台阶问题

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…