一文读懂递归算法—程序员必会算法之一

本文源自 公-众-号 IT老哥 的分享

IT老哥，一个在大厂做高级Java开发的程序员，每天分享技术干货文章

前言

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

递归

什么是递归

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

递归的优点

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

递归的缺点

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

举个例子

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

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

条件设定

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

算法实现

云服务器，云硬盘，数据库（包括MySQL、Redis、MongoDB、SQL Server），CDN流量包，短信流量包，cos资源包，消息队列ckafka，点播资源包，实时音视频套餐，网站管家（WAF），大禹BGP高防（包含高防包及高防IP），云解析，SSL证书，手游安全MTP，移动应用安全、 云直播等等。

// 寿命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 + "次故事");
}