一篇文章让你彻底搞懂递归_递归结束

只要是学过数据结构与算法的小伙伴一定都了解过递归，但是真正能够熟练运用递归的可能没多少人，我自从进入大学就听过一句话，一般能够用递归的都能够使用迭代求解，但是使用递归的是神，而使用迭代（循环）的则是普通人。
下面我将带着大家一步一步的走进递归！

1.递归使用的条件

如果你发现一个业务或者一个功能满足以下条件，则可以考虑使用递归。
1.一个问题的解可以分解为几个子问题的解；
2.这个问题与之分解之后的子问题，除了数据规模不同，求解思路完全一样；
3.存在终止条件。
但是，站在Java程序员的角度，JVM在执行方法的时候就需要对方法进行大量的压栈或出栈的操作，所以递归的空间复杂度较高，并且有堆栈溢出的风险，过多的方法调用会耗时较多，还存在一种重复计算问题。
因此，在开发过程中需要根据实际情况来决定是否使用递归。
而且，在面试的过程中，一个算法问题，如果你用递归的方式解决了，面试官一般还会要求你使用迭代循环的方式解决。

2.递归的三要素

第一要素：明确你这个函数想要干什么；
根据业务的实际需求情况来编写满足对应功能的类和函数。
第二要素：寻找递归结束条件；
递归中一般要时刻考虑递归的结束条件，即出口，否则如果无限递归下去，JVM的栈区不断的压方法，最后会导致栈溢出异常。
第三要素：找出函数的等价关系式。
将一个大问题分解为求解思路相同的多个子问题，即逐渐缩小问题的规模，直到遇到出口。

3.经典递归算法题

1.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例一：

示例二：

这里使用f(n)表示爬取n楼有多少种不同的方法。
$f(n)=\{\begin{array}{cc}1& n=1\\ 2& n=2\\ f(n-1)+f(n-2)& n⩾3\end{array}$
纯粹递归代码展示:

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }
}
1
2
3
4
5
6
7

这是单纯使用递归的算法，但是如果把这一段代码放入LeetCode里面执行，LeetCode便会提示超出时间限制，不允许通过。
出现上述问题的原因主要是在递归的过程中存在大量的重复计算问题，因此我们需要经求解过程中的中间值用HashMap集合保存起来，每当碰到一个climbStairs（i）我们定首先去定义的集合中获取，如果集合中不存在，则我们再调用递归的方式求解，并把求解的结果放入集合中存储！
带HashMap递归代码如下所示：

class Solution {
    private Map<Integer,Integer> map=new HashMap<>();
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(map.get(n)!=null)
        return map.get(n);
        else{
        int result=climbStairs(n-1)+climbStairs(n-2);
        map.put(n,result);
        return result;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

非递归代码展示：
非递归迭代求解，我们可以采用自低向下循环求解，因为最底层的climbStairs(1)与 climbStairs（2）是已知的，我们可以按照一定的变换过程逐渐将 climbStairs（n）累加出来。但是我们需要引入两个局部变量来保存当前子问题的结果。

class Solution {
    public int climbStairs(int n) {
        //循环迭代
        if(n==1) return 1;
        if(n==2) return 2;
        int result=0;
        int next=2;
        int pre=1;
        for(int i=3;i<=n;i++){
            result=next+pre;
            pre=next;
            next=result;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.斐波那契数列问题

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
注意，这里需要对求出的结果集进行取模运算！
示例一：

示例二：

这里使用f(n)表示数列第n项的值。
$f(n)=\{\begin{array}{cc}0& n=0\\ 1& n=1\\ f(n-1)+f(n-2)& n⩾2\end{array}$
1.纯粹的递归代码求解

class Solution {
    private Map<Integer,Integer> map=new HashMap<>();
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        return (fib(n-1)+fib(n-2))%1000000007;
    }
}
1
2
3
4
5
6
7
8

同样，这种方式在LeeCode汇总会超出时间限制。

2.带有Map集合的递归求解

class Solution {
    private Map<Integer,Integer> map=new HashMap<>();
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(map.get(n)!=null)
        return (map.get(n))%1000000007;
        else{
            int result=fib(n-1)+fib(n-2);
            map.put(n,result);
            return result%1000000007;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.非递归代码求解

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int result=0;
        int pre=0;
        int next=1;
        for(int i=2;i<=n;i++){
            result=(next+pre)%1000000007;
            pre=next;
            next=result;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15