如何理解和使用递归算法

一、什么是递归？

自己调用自己，当业务逻辑符合以下三个条件的时候，就可以考虑使用递归来实现。

一个问题可以分解为多个子问题；
当前问题与其子问题除了数据规模不同外，求解思路完全一样；
存在递归终止条件；

二、为什么要使用递归？

理论上，任何递归代码都可以使用非递归的方式进行实现，那么为什么还要使用递归呢？

递归求解本质上是使用系统提供的栈来实现的，由系统为我们自动递归求解；如果改成非递归的方式，那么我们其实就是在手动递归，本质上这两种方式没有任何区别。但是相同的逻辑，两份代码，递归实现明显更加地简洁，更加有利系统的维护。

三、如何使用递归？

我们以一个实际的例子来演示如何使用递归。

假设，有n个台阶，我们一步可以跨一个台阶，也可以一步跨两个台阶，那么这n个台阶总共有多少种跨法？

我们按照递归使用的三个条件来分析下：

是否可以分解为子问题？

是的，我们跨上第n阶台阶时，要么是一步一个跨上去的，要么就是一步两个跨上去的，所以问题就分解为“跨上n-1个台阶有多少种跨法”+“跨上n-2个台阶有多少种跨法”，递推公式可以表示为f(n)=f(n-1)+f(n-2);
当前问题和子问题的求解思路是否一样？

是的
是否存在终止条件？

是的，当n为1的时候，就一种跨法，当n为2的时候有两种跨法，当n为3或者4的时候，可以拆解为子问题，所以终止条件就是f(1)=1,f(2)=2;

分析完之后，我们就得到了带终止条件的递推公式，再转换为代码即可：

int countSteps(int n){
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    
    return f(n-1) + f(n-2);
}

递归的求解过程确实很难一下子就理解清楚，这是由于我们人脑的机制造成的，谁都会感觉这样。

我们应该假设子问题f(n-1)和f(n-2)已经得到求解，然后在此基础上去求解当前的问题f(n)，得到一个递推公式，如此只思考两层之间的关联关系会简单很多，千万不要试图去分解和理解每个递归层次的过程。

四、使用递归需要注意什么？

4.1 堆栈溢出

当递归调用深度过深的时候，就很容易出现栈溢出的问题，此时最好的方法就是根据业务场景逻辑和JVM的栈大小确定一个合理的最大递归深度，当超过该深度值的时候，程序抛出异常；

4.2 重复计算

子问题的子问题可能会出现重复的问题，比如f(6)=f(5)+f(4)，其中，f(5)和f(4)都会有子问题f(3)，那么f(3)应该是不需要重复计算的。

我们可以将求解过的问题结果保存到散列表中，当递归调用执行时，先检查该问题是否已经求解过了，如果是那么直接从散列表中获取结果返回即可，只有没有求解过的问题，才继续递归调用；

int countSteps(int n){
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    
    // 先从散列表中检查是否已经对f(n)求解过了
    if(resultMap.get(n) != null){
        return resultMap.get(n);
    }
    int result = f(n-1) + f(n-2);
    // 将当前问题f(n)结果保存到散列表
    resultMap.put(n,result);
    return result;
}

4.3 时空复杂度

空间复杂度方面，因为递归深度决定着栈的使用程度，所以空间复杂度为O(n)；

时间复杂度上面，虽然入栈和出栈都是O(1)，但是如果递归深度较大的话，函数上下文切换等造成的时间开销也会比较可观；

4.4 递归环

有时候，可能由于脏数据的问题，会导致递归环的存在，比如在找原始推荐人的时候，A推荐了B，B推荐了C，C推荐了D，然后有一条脏数据，导致A的推荐人是D，那么在递归寻找原始推荐人的时候，就会陷入环中，可以设置一个最大递归深度来解决这个问题。