数据结构与算法系列九(递归详解)

2019/04/10 10:10
阅读数 9

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.13.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.当子问题足够小的时候,找出终止条件

 

原文出处:https://www.cnblogs.com/itall/p/12426053.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部