什么是递归?

图片来源于网络

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

#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 条评论
登录 后参与评论

相关文章

  • 浅谈什么是递归算法

    程序调用自身的编程技巧称为递归( recursion)。递归作为一种算法在程序设计语言中广泛应用。一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法...

    五分钟学算法
  • 什么是递归--What does resursion mean?

    在Google.com.hk或者在Google.com上搜索 递归或者recursion 发现Google“抽了”,明明搜索正确,为啥还显示一个查询错误的提示?...

    Fisherman渔夫
  • 什么是递归,通过这篇文章,让你彻底搞懂递归

    Beauty begins the moment you decide to be yourself.

    好好学java
  • 2020-1-6-什么是尾递归

    递归算法想必大家都已经很熟悉了。递归算法虽然简单,但是容易导致一些性能问题,于是就有了尾递归这种优化算法。

    黄腾霄
  • 尾递归是怎么一回事?什么是尾递归?

    50%的算法问题都能通过递归来解决,倒不是说递归本身有多厉害,只是说明递归的思想让很多复杂的问题变得简单! 啥? 了解数据结构的人都知道, 树结构本身就是用递...

    zhaoolee
  • 什么是php递归函数及简单实例讲解

    递归函数即自调用函数,在函数体内部直接或者间接的自己调用自己,即函数的嵌套调用是函数本身。通常在此类型的函数提之中会附加一个条件判断叙述,以判断是否需要执行递归...

    全栈程序员站长
  • 大家都知道递归,尾递归呢?什么又是尾递归优化?

    今天,我们来聊聊递归函数。为啥突然想到递归?其实就从电影名字《恐怖游轮》《盗梦空间》想到了。

    程序猿石头
  • 为什么说递归是码农的一道分水岭?

    为什么这一篇要先写递归这种思想呢?初衷主要是因为最近在写设计模式中的组合模式。这个设计模式的实现呢,需要使用到树形数据结构,而树形结构又是天生的递归结构,所以这...

    程序IT圈
  • 面试官:递归是个什么东东?

    递归是一种编程模式,在一种任务可以自然地拆分为相同类型的多个任务,但更简单的情况下很有用。或者,当一个任务可以简化为一个简单的动作以及该任务的一个更简单的变体时...

    公众号---人生代码

扫码关注云+社区

领取腾讯云代金券