什么是递归?

图片来源于网络

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

#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],等等。用递归来解决这些问题,往往几行代码就搞定了一些看起来相当”吓人“的问题。 当然,递归的性能问题是另一回事,栈的分配,函数调用代价都是在具体工程实践中要考虑的。 但现在只是讨论递归思想的话,不妨先放下那些,欣赏下递归的美。

----以上均来自网友回答

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

设计模式(11)——模板方法模式(Template Method Pattern,行为型)

模板方法模式(Template Method Pattern)属行为型,在一个方法中定义一个算法骨架,而将一些步骤延迟到子类中,使子类可以不改变算法结构即可重定...

902
来自专栏北京马哥教育

教程 | 比Python快100倍,利用spaCy和Cython实现高速NLP项目

相关 Jupyter Notebook 地址:https://github.com/huggingface/100-times-faster-nlp

1030
来自专栏JavaQ

写这样的方法让人很反感

写作文要做到段落清晰、每段思路流畅、每段主旨明确,要有一条清晰的线穿插整篇内容,编写程序代码和写作文是一个套路。一个类就像一篇小作文,类的单一职责就是小作文要叙...

3467
来自专栏JadePeng的技术博客

知识图谱学习笔记(1)

RDF(Resource Description Framework),即资源描述框架,其本质是一个数据模型(Data Model)。它提供了一个统一的标准,用...

1970
来自专栏程序人生

谈谈数据结构

沃斯大神说过,程序 = 算法 + 数据结构。 程序君认为,等式的右边,数据结构的权重要大于算法。数据结构定义好,基本上,你所用的算法也就确定了,算法的时间复杂度...

3787
来自专栏小樱的经验随笔

51Nod 1016 水仙花数 V2(组合数学,枚举打表法)

1016 水仙花数 V2 基准时间限制:1 秒 空间限制:131072 KB 分值: 160         难度:6级算法题 水仙花数是指一个 n 位数 ...

2937
来自专栏CDA数据分析师

10个应该早点知道的Python技巧

我的这一生都在编程,但是我没有成为一名程序员。最初,我的大部分工作都是用Visual Basic来完成的,还包括一些其它语言工具,比如R语言,C语言、JavaS...

2909
来自专栏web编程技术分享

来谈谈JAVA面向对象 - 继续说多态~

2985
来自专栏小詹同学

Leetcode打卡 | No.18 四数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1132
来自专栏Java学习网

10种简单的Java性能优化学习

10种简单的Java性能优化学习 你是否正打算优化hashCode()方法?是否想要绕开正则表达式?Lukas Eder介绍了很多简单方便的性能优化小贴士以及扩...

3456

扫码关注云+社区

领取腾讯云代金券