一文搞懂什么是递归，程序员必会算法之一

发表于

前言

今天我们来讲讲递归算法，递归在我们日常工作中是比较常见且常用的算法，面试中面试官也经常会让我们手写递归算法。由此可见递归算法的重要性。

递归

什么是递归

简单来说递归就是方法自己调用自己，每次调用时传入不同的变量。一直到程序执行到指定的出口时停止调用本身，并将结果层层返回。

递归的优点

递归的核心思想就是将一个大问题，拆解成一个小问题，然后将小问题再次拆解，层层拆分从而简化问题。这种设计理念可以简化重复的代码让程序变得更加简洁。

递归的缺点

  • 使用递归算法时每次方法的调用都需要在栈中开辟出一个空间保存相关数据，频繁的压栈、弹栈会导致效率变低。
  • 使用递归算法解决问题必须要有出口，不然就形成死循环了。好好的递归变成了“死归”！
  • 递归的调用次数不宜过多不然会造成栈溢出。

举个例子


从前有座山，山里有座庙，庙里有位老和尚，老和尚在干嘛呢？老和尚在讲故事。讲的什么故事呢？从前有座山，山里有座庙 ……

这是我们耳熟能详的故事，我们就通过这个案例来讲讲递归。

条件设定

  • 老和尚讲故事，老和尚寿命是5岁
  • 每讲一次寿命就减一岁
  • 当岁数减到0的时候，老和尚就圆寂了，就停止了讲故事
  • 最终返回总共讲故事的次数

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
复制代码// 寿命5岁
private static Integer life = 5;

// 讲故事次数
private static Integer storyNum = 0;

public static Integer tellStory(Integer life) {

    if (life > 0) {
        System.out.println("从前有座山，山里有座庙，庙里有位老和尚，老和尚在干嘛呢？老和尚在讲故事。讲的什么故事呢？");
        -- life;
        // 老和尚还没圆寂，继续讲故事，这就是递归
        tellStory(life);
    } else {
        System.out.println("老和尚圆寂了，没办法在给大家讲故事了！");
        return storyNum;
    }
    return ++ storyNum;
}

public static void main(String[] args) {
    Integer num = tellStory(life);
    System.out.println("老和尚总共讲了" + num + "次故事");
}

递归结果



IT 老哥

一个在大厂做高级Java开发的程序猿

❝
关注微信公众号：IT 老哥

❞

❝
回复：Java 全套教程，即可领取：Java 基础、Java web、JavaEE 全部的教程，包括 spring boot 等

❞

❝
回复：简历模板，即可获取 100 份精美简历

❞

❝
回复：Java 学习路线，即可获取最新最全的一份学习路线图

❞

❝
回复：Java 电子书，即可领取 13 本顶级程序员必读书籍

❞

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%