您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

深究递归和迭代的区别、优缺点及实例对比

时间:2019-12-25 10:16:14  来源:  作者:

1.迭代是人,递归是神!

从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。

从概念上讲,递归就是指程序调用自身的编程思想,即一个函数调用本身;迭代是利用已知的变量值,根据递推公式不断演进得到变量新值的编程思想。

2.递归

递归就是函数自己调用自己。

2.1构成递归需具备的条件:

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

2.2递归的基本原理

第一:每一级的函数调用都有自己的变量。

第二:每一次函数调用都会有一次返回。

第三:递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四:递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五:虽然每一级递归都有自己的变量,但是函数代码并不会得到复制。

2.3递归优缺点

 

深究递归和迭代的区别、优缺点及实例对比

 

2.4编写一个递归函数

  • 这个递归函数的功能是什么,怎样调用这个函数,即设计好递归函数的返回值和参数列表
  • 什么时候应该结束这个递归,它的边界条件(出口)是什么(边界条件)
  • 在非边界情况时,怎样从第n层转变成第n+1层(递推公式)

例:

int f(int n) {  //出口    if (n > 0) {        return n + f(n - 1);    } else {        return 0;    }}

解析:

深究递归和迭代的区别、优缺点及实例对比

 

具体步骤:

深究递归和迭代的区别、优缺点及实例对比

 

递归递归,有递就得有归(出口),只递不归会导致程序崩溃。

要得到n - 1的积直接调用 f(x) 这个函数就行了,完全不需要思考这个函数怎么执行的。

3.例题:走楼梯

3.1题目描述:

一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法。I第一行输入T,表示有多少个测试数据。接下来T行,每行输入一个数n,表示台阶的阶数。
输出时每一行对应一个输出。

假如一共有三级台阶,一共有多少种走法?

深究递归和迭代的区别、优缺点及实例对比

 

假设有n级台阶,一共有多少种走法?

深究递归和迭代的区别、优缺点及实例对比

 

当n > 2 时,如果走1级有多少种走法 + 如果走2级有多少种走法,就是n级台阶所有的走法。

4.求n!递归法

int fun(int n) {    if (n == 1) {        return 1;    } else {        return n * fun(n - 1);    }}

5.求n!迭代法

int fun(int n) {    int x = 1;    for (int i = 2; i <= n; i++) {        x *= i;    }    return x;}

6.迭代

迭代与普通循环的区别是:迭代时,循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。

递归与普通循环的区别是:循环是有去无回,而递归则是有去有回(因为存在终止条件)。

在循环的次数较大的时候,迭代的效率明显高于递归。

6.1现实中的迭代

迭代的方式有所不同,假如有个产品要求6个月交货,我在第一个月就会拿出一个产品来,当然,这个产品会很不完善,会有很多功能还没有添加进去,bug很多,还不稳定,但客户看了以后,会提出更详细的修改意见,这样,你就知道自己距离客户的需求有多远,我回家以后,再花一个月,在上个月所作的需求分析、框架设计、代码、测试等等的基础上,进一步改进,又拿出一个更完善的产品来,给客户看,让他们提意见。
就这样,我的产品在功能上、质量上都能够逐渐逼近客户的要求,不会出现我花了大量心血后,直到最后发布之时才发现根本不是客户要的东西的情况。

6.2优势

这个过程也很像打游戏,你刚开始玩,一下子就输了,但是随着你玩的次数越来越多,你的技艺就越来越精湛,而这个结果,不是你在开始玩游戏的时候,规划出来的,而是在你玩的过程中,通过不断的输不断的输,练出来的。

所以,你能达成的结果,都是在你做的过程中,不断试错,不断调整,不断精进,最后自然而然得到的一个结果。

所以,我们不能把迭代简单的理解为“升级”。

升级,更多描述的是一个结果,是一种直接的,一次性的,达成的一个目标,是一种线性的进程。

而迭代,是通过无数次,不断的,重复的,接近一个目标,折返接近,再折返再接近,最终达到目标。它不是一次性完成的,是通过不断重复的,但每次重复又比之前更好一点,这样一种非线性的进程。

现在我们把“迭代”的关键词拆解一下:

1.重复:

不断的重复做,而不是一次性的完成。

2.改进

在做的过程中不断的改进、调整、优化。

3.认知升级

迭代的过程就是不断提高认知的过程,升级只是这个过程的一个结果。



Tags:深究递归   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1.迭代是人,递归是神!从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。从概念上讲,递归就是指程序调用自身的编程思想,即一个函...【详细内容】
2019-12-25  Tags: 深究递归  点击:(72)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条