首页 > 其他分享 >什么是递归?

什么是递归?

时间:2024-05-20 14:20:11浏览次数:30  
标签:递归 Recursion 什么 阿珏 打开 一扇门 扇门

Tips:当你看到这个提示的时候,说明当前的文章是由原emlog博客系统搬迁至此的,文章发布时间已过于久远,编排和内容不一定完整,还请谅解`

什么是递归?

日期:2017-8-9 阿珏 谈天说地 浏览:1616次 评论:5条


图片来源于网络

一上来你肯定觉得读这句话好绕,好吃力。 其实你用递归来读就很简单了: 递归要有一个终点(小鲤鱼)
当递归尚未达到终点的时候,函数会反复调用自己。
显然,输出"我的小鲤鱼"这句话是递归终止条件。
那么写成代码就是:


#include <stdio.h>
void Recursion(int depth){
    printf("抱着");
    if (!depth) printf("我的小鲤鱼");
    else Recursion(--depth);
    printf("的我");
}
int main(){
    printf("吓得我抱起了\n");
    Recursion(2);
    putchar('\n');
}
目前我找到的对递归最恰当的比喻,就是查词典。我们使用的词典,本身就是递归,为了解释一个词,需要使用更多的词。当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词,可惜,第二个词里仍然有不懂的词,于是查第三个词,这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头,然后你开始后退,逐个明白之前查过的每一个词,最终,你明白了最开始那个词的意思。。。

箭头线代表程序实际运行步骤。


看了楼上很多答案,大多偏重于描述 递归 的现象,而没说明为什么要用递归,递归的思想到底是什么。前阵子刚好看了点东西,试着整理下,如有错误之处,请不吝指正。

  • 什么是递归?
1. 定义
Wiki [1]: Recursion is the process of repeating items in a self-similar way.
具体到计算机中去 [2]:
递归 (英语:Recursion),又译为 递回 ,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

英文的Recursion从词源上分析只是"re- (again)" + "curs- (come, happen)" 也就是重复发生,再次重现的意思。 而对应的中文翻译 ”递归“ 却表达了两个意思:”递“+”归“。 这两个意思,正是递归思想的精华所在。从这层次上来看,中文翻译反而更达意。

2. 跟循环的区别

单看上面wiki的定义,貌似跟通常所说的无限死循环很像,他们的区别在哪?
递归是静中有动,有去有回。
循环是动静如一,有去无回。

举个例子,给你一把钥匙,你站在门前面,问你用这把钥匙能打开几扇门。

递归:你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开,。。。, 若干次之后,你打开面前一扇门,发现只有一间屋子,没有门了。 你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这钥匙开了几扇门。

循环:你打开面前这扇门,看到屋里面还有一扇门,(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,(前面门如果一样,这门也是一样,第二扇门如果相比第一扇门变小了,这扇门也比第二扇门变小了(动静如一,要么没有变化,要么同样的变化)),你继续打开这扇门,。。。,一直这样走下去。 入口处的人始终等不到你回去告诉他答案。

3. 递归思想

递归就是有去(递去)有回(归来)。

具体来说,为什么可以”有去“?
这要求递归的问题需要是可以用同样的解题思路来回答类似但略有不同的问题(上面例子中的那一把钥匙可以开后面门上的锁)。

为什么可以”有回“?
这要求这些问题不断从大到小,从近及远的过程中,会有一个终点,一个临界点,一个baseline,一个你到了那个点就不用再往更小,更远的地方走下去的点,然后从那个点开始,原路返回到原点。

这篇博文[3]作者归纳为:
递归的基本思想是 把规模大的问题转化为规模小的相似的子问题来解决 。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数 必须有明显的结束条件 ,这样就不会产生无限递归的情况了。

4. 什么时候需要用递归?

当有些问题的定义本身就是递归形式的时候,最是适合用递归来解决。

计算机专业的同学最最熟悉的莫过于” “的定义了[4,5]。还有一些定义,比如阶乘,Fibonacci数列[6],等等。用递归来解决这些问题,往往几行代码就搞定了一些看起来相当”吓人“的问题。 当然,递归的性能问题是另一回事,栈的分配,函数调用代价都是在具体工程实践中要考虑的。 但现在只是讨论递归思想的话,不妨先放下那些,欣赏下递归的美。



----以上均来自网友回答 本博客所有文章 如无特别注明 均为原创。 作者: 阿珏 , 复制或转载请 以超链接形式 注明转自 阿珏博客
原文地址《 什么是递归?

网友评论:

Railgun丶无限 2年前 (2019-03-14)
斐波那契用递归是一定会爆栈的,而且非常慢,所有的递归都一定有它的非递归写法(当然效率上有的可能快有的就不一定),对于运算的值只依赖于参数的函数如斐波那契,应该采用记忆化思想……
但是递推有时候真的比递归快啊~(逃

阿珏 2年前 (2019-03-14)
@Railgun丶无限:大学生就是不一样[#aru_9]

Railgun丶无限 2年前 (2019-03-14)
@阿珏:可我不仅只是高中还很可能就要没大学上了啊Orz

阿珏 2年前 (2019-03-14)
@Railgun丶无限:这波猜错了QAQ

天津网站建设 4年前 (2017-08-15)
文章挺不错的,谢谢博主。

标签:递归,Recursion,什么,阿珏,打开,一扇门,扇门
From: https://www.cnblogs.com/Ajue/p/18201812

相关文章

  • 你知道什么是二次元吗?
    当你看到这个提示的时候,说明当前的文章是由原emlog博客系统搬迁至此的,文章发布时间已过于久远,编排和内容不一定完整,还请谅解你知道什么是二次元吗?日期:2016-11-5阿珏二次元浏览:3183次评论:3条你不懂二次元,所以你不明白,被当成异类和别人眼里的怪物的感受。你不......
  • LLM-文心一言:什么是电网WAMS?
    电网WAMS即广域测量系统(WideAreaMeasurementSystem),是基于同步向量技术构成的新一代电网动态监测和控制系统。WAMS的信息来源于PMU(相量测量单元)所采集的精确实时和同步信息,因此具有异地高精度同步向量测量、高速通信和快速反应等技术特点,非常适合大规模电网调度。它为电网实时......
  • 3d渲染图用什么软件好?初学者如何选择正确的 3D 渲染软件?
    目前市面上存在许多3D渲染软件,但是对于初学者来说,往往难以决定哪一款最适合自己。小编为大家盘点了近几年市面上主流的几款渲染软件,并总结了这些软件的优势、上手难度和适合行业。一、影视动画、建筑师和室内设计、产品设计:3DMAX3dsMax是一款由Autodesk公司开发的的三维建模、......
  • LLM-文心一言:什么是SCADA系统
    SCADA系统,即数据采集与监视控制系统,是一种基于计算机的生产过程控制与调度自动化系统。它主要应用于电力、冶金、石油、化工、燃气、铁路等领域的数据采集与监视控制以及过程控制等诸多领域。在电力系统中,SCADA系统的应用最为广泛,技术发展也最为成熟。SCADA系统具有实时监控功能,......
  • 一个页面从输入URL到加载显示完成,这个过程发生了什么?
    目录一、解析URL1、流程2、URL格式:3、示例二、浏览器封装HTTP请求报文1、流程2、HTTP请求报文例子3、封装三、DNS解析1、缓存判断1.1、浏览器缓存1.2、操作系统缓存1.3、路由器缓存2、递归查询至ISPDNS服务器3、迭代查询过程4、保存结果至各级缓存四、建立TCP连接(三次握手)1、三次......
  • react的 Hook ,useReducer 是什么
    useReducer 是React中的一个Hook,用于管理组件的状态。它提供了一种更复杂的状态管理机制,适用于那些状态逻辑较为复杂、包含多个子值的情况。与 useState 不同,useReducer 基于一个叫做reducer的函数来更新状态。Reducer接收当前的状态和一个表示要进行的操作的动作对象,......
  • 二叉树 | 递归法 101.对称二叉树
    leetcode101.对称二叉树题目101.对称二叉树给你一个二叉树的根节点root,检查它是否轴对称。解题思路递归法,判断左节点的左孩子是否可以翻转成右节点的右孩子(左节点的左孩子==右节点的右孩子,左节点的右孩子==右节点的左孩子)递归三步骤:1、确定递归函数的入参和返回值......
  • 二叉树的递归遍历 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历
    leetcode144.二叉树的前序遍历题目xxx解题思路实现代码leetcode145.二叉树的后序遍历题目xxx解题思路实现代码leetcode94.二叉树的中序遍历题目xxx解题思路实现代码......
  • PHP的多样化执行方式(parallel PHP多线程实现,原生协程实现,多进程实现,ZTS、NTS、TS又是
    进程、线程、协程进程:应用程序的启动实例,运行起的代码叫进程,有独立的内存空间,类比工厂的P个(P=1单进程,P>1多进程)车间。线程:线程是CPU调度的最小单位,是进程内的执行单元,多个线程共享所属进程的资源。类比车间内的T个员工(T=1单线程,T>1多线程)车间。协程:类似线程,协程是用户态(CPU受......
  • 解释下什么是事件代理?应用场景?
    一、是什么事件代理,俗地来讲,就是把一个元素响应事件(click、keydown......)的函数委托到另一个元素前面讲到,事件流的都会经过三个阶段:捕获阶段->目标阶段->冒泡阶段,而事件委托就是在冒泡阶段完成事件委托,会把一个或者一组元素的事件委托到它的父层或者更外层元素上,真正绑定......