数据结构与算法系列九（递归详解）

1.引子

1.1.为什么要学习数据结构与算法？

有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！

有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写的代码不也能“飞”起来吗？

于是问题来了：为什么还要学习数据结构与算法呢？

#理由一：
    面试的时候，千万不要被数据结构与算法拖了后腿
#理由二：
    你真的愿意做一辈子CRUD Boy吗
#理由三：
    不想写出开源框架，中间件的工程师，不是好厨子

1.2.如何系统化学习数据结构与算法？

我想好了，还是需要学习数据结构与算法。但是我有两个困惑：

1.如何着手学习呢？

2.有哪些内容要学习呢？

学习方法推荐：

#学习方法
1.从基础开始，系统化学习
2.多动手，每一种数据结构与算法，都自己用代码实现出来
3.思路更重要：理解实现思想，不要背代码
4.与日常开发结合，对应应用场景

学习内容推荐：

数据结构与算法内容比较多，我们本着实用原则，学习经典的、常用的数据结构、与常用算法

#学习内容：
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

2.考考你

在上一篇【数据结构与算法系列八（递归见面礼）】中，通过两个小案例：

1.求最终推荐人

2.电影院看电影

相信你已经对递归有一个直观的认识了。那么这一篇我们来对递归做一个详细的分析，比如以下这几个问题，如果你都知道，那么恭喜你！你都会抢答了（开个玩笑，这是黑土大爷说的：不是卖车，就是卖拐，对吧）。

言归正传，关于递归，我们只需要搞清楚以下几个问题，就算是完全掌握了。很简单有没有？

#考考你：
1.你知道哪些问题适合用递归解决吗？
2.你知道编写递归代码的关键步骤吗？

3.案例

3.1.递归解决的问题模板

我们说每一种数据结构与算法，都是在特定问题域下的产物；也就是说每一种数据结构与算法，都有它们各自适用的问题场景。

关于递归，结合上一篇：求最终推荐人、电影院看电影案例，我们可以归纳如下：

1.问题可以分解为子问题

简述：

对于一个问题的求解，本身可以被分解为更小的子问题

案例：

电影院案例：我们在哪一排的问题，可以分解为我们的前一排人在哪一排的子问题

2.问题的求解，与分解后的子问题，求解思路一致

简述：

问题本身的求解思路，与分解后的子问题求解思路一致

案例：

电影院案例：求解我们在哪一排的问题思路，与求解我们前一排人在哪一排的思路一致

3.问题的求解，存在终止条件

简述：

注意，这一条很重要，递归一定要有明确的终止条件，否则就等于死循环了

案例：

电影院案例：存在终止条件，如果是第一排，则f(1)=1

3.2.编写递归代码关键步骤

知道了递归适合解决的问题，那么在实际软件开发中，我们该如何更有效率的编写递归代码呢？有没有什么套路，或者模板。答案是有。

编写递归代码，有两个关键步骤：

1.找出递推公式

简述：

前面我们说了，递归适合于将问题分解为子问题，然后问题本身的求解，与子问题求解思路一致。你需要仔细琢磨并理解这句话的含义，这句话是精髓。如果你理解了，你会发现这其实是一个重复性的问题。

那么顺着这个思路，我们只需要将子问题，在继续分解问为更小的子问题......一直到子问题不能再分解为止。

这里需要提醒一个常见的思维误区：我们在分解问题的时候，千万不要在大脑里去重现每一个分解步骤，这样容易把自己绕进去：走火入魔。毕竟人类的大脑只适合平铺直叙的思维方式，重复性的东西更适合电脑，对吧。你只需要找出不能再分解的最小子问题，然后解决它就对了。

案例：

电影院案例：f(n)=f(n-1)+1

2.找出终止条件

简述：

关于递归就是一个不断分解子问题，与求解子问题的过程。因此一定要存在明确的终止条件。一定要找到它，不然就死循环了。

案例：

电影院案例：f(1)=1

3.3.走台阶案例

我们通过一个稍微复杂些的案例，来巩固3.1与3.2两节的内容。假设有一个n阶的台阶，小明每一步可以走1个台阶，或者走2个台阶。求小明走完台阶，总共有多少种走法？

3.3.1.找出递推公式

我们首先尝试分析，有这么几个前提：

1.总台阶数是n

2.走台阶的方式，一次可以走1个台阶，或者一次可以走2个台阶

那么根据递归求解过程：分解子问题。不过这个案例稍微复杂一些，我们可以假设小明第一步只走1个台阶，是一种走法，即 f(n-1)；第一步走2个台阶，又是一种走法，即f(n-2)。

这样一来，我们就可以得出递推公式，走完n个台阶的走法f(n)，等于第一步走1个台阶的走法f(n-1)，加上第一步走2个台阶的走法f(n-2)。即：

#走n个台阶的递推公式
f(n)=f(n-1)+f(n-2)

3.3.2.找出终止条件

寻找终止条件的前提是，假设子问题不能再分解为更小的子问题的时候，有明确的终止条件。我们继续尝试分析：

1.我们假设最后只剩下1个台阶的情况，只有一种走法，即：f(1)=1

2.我们假设最后剩下2个台阶的情况，一次可以走1个台阶，是一种走法；一次可以走2个台阶，又是一种走法。那么剩下2个台阶的走法是：f(2)=2

#走n个台阶的终止条件
只剩下1个台阶：f(1)=1
剩下2个台阶：f(2)=2

3.3.3.实现代码

有了递推公式，与终止条件，再来编写递归代码就是水到渠成的事情了，很简单了有没有

/**
* 递归求解走n阶抬价的走法：
*  1.求解递推公式
*      1.1.前提：每次可以走1步台阶，或者2步台阶
*      1.2.第一步走法是关键：
*          1.2.1.如果第一步走1步台阶，则剩下n-1步台阶
*          1.2.2.如果第一步走2步台阶，则剩下n-2步台阶
*      1.3.根据1.2.1与1.2.2得出：
*          1.3.1.递推公式：f(n) = f(n-1) + f(n-2)
*          1.3.2.f(n-1)表示剩下n-1步台阶走法
*          1.3.3.f(n-2)表示剩下n-2步台阶走法
*
*  2.求解终止条件
*      2.1.如果只剩下1步台阶，则f(1)=1
*      2.2.如果剩下2步台阶，则f(2)=2，有两种走法
* @param n
*/
public static int walkingMethod(int n){
    // 终止条件f(1)=1
    if(n == 1) return 1;

    // 终止条件f(2)=2
    if(n == 2) return 2;

    return walkingMethod(n - 1) + walkingMethod(n -2);
}

4.讨论分享

#考考你答案：
1.你知道哪些问题适合用递归解决吗？
  1.1.如果一个问题，满足三个条件，适合用递归解决
    a.问题本身，可以分解为子问题
    b.问题本身的求解思路，与分解后的子问题求解思路一致
    c.求解问题，本身存在明确的终止条件
     
2.你知道编写递归代码的关键步骤吗？
  2.1.编写递归代码的关键步骤，有两步
    a.根据分解后的子问题，找出递推公式
    b.当子问题足够小的时候，找出终止条件