关联文章:
?? 本篇是数据结构与算法的第 6 篇,从这篇种我们将深入了解递归算法,这可能是一篇分水岭的博文,因为只有在理解递归的基础上,我们才可能更轻松地学习树的数据结构,实际上数据结构系列书籍中递归并没有讲得特别通俗易懂,博主目前看过的书籍中分析递归最好的是日本人吉城浩写的《程序员的数学》,因此本篇会结合个人对递归的理解以及该书中的两个博主认为比较合适例子来分析,本篇可能不会涉及太多的代码,相反的,更希望呈现给大家一种通俗易懂的思维方式,重在理解,毕竟理解得越多,需要记忆自然也就越少了,以下是主要知识点
现在我们先不需要知道递归是什么,也没必要,我们先来看一个非常经典的游戏—汉诺塔,该游戏是数学家爱德华卢卡斯于 1883 年发明的,游戏的规则如下,有三根细柱(A、B、C),A 柱上套着 6 个圆盘,圆盘的大小都不一样,它们按照从大到小的顺序自下而上地摆放,现在我们需要把 A 柱上的圆盘全部移动到 B 柱上去,并且在移动时有如下约定:
此时约定将一个圆盘从一根柱子移动另一根柱子算移动 "1" 次,那么将 6 个圆盘全部从 A 移动到 B 至少需要移动多少次呢?模型如下图:
?? 图虽然很清晰,但我们依然无法立即找到特别清晰的解法,既然如此,我们就尝试先把问题的规模缩小点,把 6 个圆盘改为 3 个圆盘,先找出 3 层汉诺塔的解法,模型变为下图:
??3 层汉诺塔的解法就相对来说简单多了,我们要把 3 个圆盘全部从 A 移动到 B,只需要先将最小的圆盘从 A 移动到 B,然后将次小的圆盘从 A 移动到 C,接着再把最小的圆盘从 B 移动到 C,然后把最大的圆盘从 A 移动到 B,接着把最小盘从 C 移动到 A,在把次小盘从 C 移动到 B,最后把最小盘从 A 移动到 B 即可,这样我们就完成了 3 此汉诺塔的解法了。这里我们把 3 个圆盘从小到大分别设为 a,b,c,那么其移动过程如下:
- /**
- 元素 过程
- a A->B
- b A->C
- a B->C
- c A->B
- a C->A
- b C->B
- a A->B
- 移动7次完结..
- **/
整个过程如下图所示:
从上图中,我们很容易理解 3 层汉诺塔的解法,但是细想一下会发现这 7 次动中我们好像在做重复的事情:移动圆盘,只不过方向时而不同罢了。重新回顾一下①②③⑤⑥⑦的移动过程,然后把它们分为如下两种情况:
我们发现这个过程移动的操作是几乎一样的,只不过是移动的方向不同了,A->C 和 C->B 两种,其过程如下图:
从图确实可以看出虽然两次移动的目的地不相同,但是两次移动的操作却是非常相似的,而且我们发现如果把 3 次移动看成是 "移动 2 个圆盘" 的操作就是 "2 层汉诺塔的解法",也就是说在解决 3 层汉诺塔的过程中,我们使用了 "2 层汉诺塔的解法"。既然如此,那是不是意味着解决 "4 层汉诺塔" 的过程中可以使用解决 "3 层汉诺塔的解法" 呢?嗯,确实是如此的,这就是汉诺塔的解法规律,没错,我们已经发现这种规律!这样的话,我们解决前面的 6 层汉诺塔的问题时,只需要先解决 5 层汉诺塔的问题,然后利用 5 层汉诺塔的解法来解决 6 层汉诺塔的问题即可!我们来看看利用 5 层汉诺塔解出 6 层汉诺塔的过程,如下:
从图中我们可以看出(a)和(c)就是 5 层汉诺塔的解法,为了解出 6 层汉诺塔需要使用到 5 层汉诺塔的解法,因此只要 5 层汉诺塔被解出,6 层汉诺塔也就迎刃而解了。而 5 层汉诺塔的解法呢?没错利用我们前面发现的规律,用 4 层汉诺塔的解法去解出 5 层汉诺塔,如下过程:
这样 5 层汉诺塔就被解出了,而 4 层汉诺塔则可以利用同样的解法即使用 3 层汉诺塔的解法,3 层汉诺塔再利用 2 层汉诺塔的解法…….. 依次类推即可,到此便已解出 6 层汉诺塔,实际上我们知道有了 6 层汉诺塔的解法自然就可以很轻松地解出 7 层汉诺塔,8 层汉诺塔…….N 层汉诺塔,也很容易发现这种利用已知的 N-1 层的解法来解决 N 层的问题的解题方式,它们每一层的解法结构都是相同即利用前一个已解决的问题结果来解决后一个问题。通过这种思考的方式,我们来总结一下 N 层汉诺塔的解法,不再使用具体的 ABC 三根柱子,而是将它们设为 x、y、z。这样的话,x、y、z 在不同的情况下会不固定对应 ABC 中的某一根。这里以 x 为起点柱,y 为目标柱,z 为中转柱,然后给出解出 N 层汉诺塔的过程。利用 z 柱将 n 个圆盘从 x 柱转移到 y 柱的解法如下:
从上述过程可知为了解出 n 层汉诺塔,我们同样需要先解出 n-1 层汉诺塔,为更通用地表示解出 n 层汉诺塔的移动次数,将其设为 H(n)。利用上述步骤,则有如下关系:
?? 在数学上我们将这种 H(n) 和 H(n-1) 的关系式取了个名称,叫做递推公式,即已知 H(0), 由 H(n-1) 构成 H(n) 的方法也必然是已知的,只要依次计算便可以得出,如 6 层汉诺塔的递推过程如下:
这样我们也就知道了 6 层次汉诺塔的最少移动次数为 63 次(关于 2^n-1 的公式只是总结出更为简单的计算方式摆了)。到此我们来重新梳理一下汉诺塔的整个解题过程,在解出 6 层汉诺塔前,我们由于一时找不到解决的方法,因此先尝试解出更为简单 3 层汉诺塔的,而在这个过程中,我们慢慢发现了解决汉诺塔问题的通用规律,即使用 n-1 层的解法来解决 n 层汉诺塔的思考方式, 通过这种思考方式最终成功地解决了 6 层汉诺塔的问题。而实际上我们利用的这种思考方式的本质就是将复杂的问题转换为较为简单的同类问题 (回忆一下汉诺塔的问题解法) 然后再找出解决方法最终利用简单同类问题解出复杂问题的过程,而这种思维的方式就是递归!!是的,没错!递归不是算法而是一种思考的思维方式,只不过我们将这种递归思维方式采用程序来解决时,该程序被称为递归算法罢了,而递归本身是一种思考问题的思维方式!到此我们对递归是否有些焕然大悟的感觉呢?或对递归有些许的理解了吧?
有了上述的分析,我们就可以这样去理解和使用递归,假设现在碰到了一个很复杂的难题,我们也明白'简单问题易解'的道理,那么此时就可以利用类似于汉诺塔的解题的思考方式,即判断能否将目前复杂的问题转换为较为简单的同类问题呢?可以的话,就先转换为简单同类的问题来解决,然后再利用简单的同类问题解法来解决复杂的同类问题,这就恰恰就是递归思维方式的精髓所在,嗯,这就是递归!大家现在是不是已开始理解递归了呢?我们在回顾一下汉诺塔问题的解法,以便加深对递归的理解,如下图:
上图很清晰表现出 n 层汉诺塔的解法过程,通过复杂问题化为同类简单问题来求解,上述的图形还有一个名称叫做递归结构,根据该结构我们就可以建立起之前 H(n) 递推公式了,很显然发现递归结构并建立递推公式的过程十分重要,这样有助于我们把握本质问题即通过 n-1 层汉诺塔的解法来解决 n 层汉诺塔的问题,这样的发现能力需要我们有比较敏锐的洞察力和思维能力,这就需要我们再遇到复杂问题时,多采用递归的思维(复杂问题简单化)方式去思考,去挖掘规律。ok~,到此相信我们对递归已有比较清晰的了解了吧。接下来我们看看如何使用程序来实现递归算法并解决汉诺塔的问题。
通过前面的分析,我们明白所谓的递归不过就是把复杂问题简单化的思维方式,而这种思维方式从程序语言的角度出发则称为递归算法,它通过程序的函数方法直接或者间接调用函数自身的过程,回忆一下前面分析汉诺塔的递推公式:H(n)=H(n-1)+1+H(n+1)
我们通过程序的递归算法实现汉诺塔如下:
从代码可以发现递归算法的踪影:
因此到此我们也就明白了,递归思维在程序中的体现即为递归算法,而递归算法本身在程序内部的实现就是函数调用自身函数,这样大家总该理解递归算法了吧。这里有点要提醒大家的是,不要陷入程序递归的内部去思考递归算法,记住要从递归思维的本质 (复杂问题简单化) 出发去理解递归算法,千万不要去通过试图解析程序执行的每一个步骤来理解递归(解析程序的执行是指给函数一个真实值,然后自己一步步去推出结果,这样的思考方式是错误的!),那样只会让自己得到伪理解 (没有真正理解) 的结果。记住!递归并不是算法,是一种复杂问题简单化的思维方式,而这种思维方式在程序中的体现就递归算法!递归算法在实现上就是函数不断调用自身的过程!
通过前面大篇幅的分析,到此我们总算是理解递归了,那么接下来我们给出递归的正式定义,相信有了上述基础,理解递归的正式定义还是比较轻松的,递归其实是数学中一种重要的概念定义方式,而递归算法则是针对程序设计而言的,即不同角度的两种称呼但本质是一样的。
递归的定义 (从数学的角度):用一个概念的本身直接定义自己。如阶乘函数 F(n)=n! 可以定义为:
关于阶乘这里简单说明一下
- 阶乘是什么?1 x 2 x 3 x 4 x 5 = 5 ! 这里的5 ! 就称为5的阶乘,之所以称为阶乘是因为乘数呈阶梯状递减而得名,如下:5 ! =5 x 4 x 3 x 2 x 1 = 120 4 ! =4 x 3 x 2 x 1 = 24 3 ! =3 x 2 x 1 = 6 2 ! =2 x 1 = 2 1 ! =1 = 1 0 ! =1注意0的阶乘0!被定义为1,这是数学里的规定。n的阶乘如下:n != n x(n - 1) x(n - 2) x…x 2 x 1很显然n ! 是一种递推公式,也符合递归思维,因此有:当n = 0时,n ! =1;当n >= 1时,n x(n - 1) ! 可以发现它使用了阶乘 (n - 1) ! 来定义阶乘n ! ,是不是跟汉诺塔很相似?没错,确实是递归思维的体现。ok~,关于阶乘我们就简单了解这些。
递归算法的定义 (从程序的角度):任何调用自身函数的过程都可以称为递归算法 (前面实现的汉诺塔程序就是一个很好的例子)。这里需要注意的是递归必须满足以下两个条件:
边界条件和递推通式是递归定义的两个基本要素,缺一不可,并且递归通式必须在有限次数内运算完成达到边界条件以保证能够正常结束递归,得到运算结果。好~,以上便是递归的定义,还是那句话理解好递归思维 (复杂问题简单化) 才是重点!
如果上述的分析都明白了,那就说明你已掌握了递归,但为了加深对递归的理解,我们再来看一个思考题(来自程序员的数学思考题),题目是这样的,假如动物中有一种特殊的种类,它出生 2 天后就开始以每天 1 只的速度繁殖后代。假设第 1 天,有 1 只这样的动物(该动物刚出生,从第 3 天开始繁殖后代)。那么到第 11 天,共有多少只呢?
- 我们先来按一般顺序思考,先不要考虑第11天,先从第1天开始,看能不能找出规律:【第1天】只有1只动物【第2天】只有1只动物,还没有繁殖后代,总量为1【第3天】第1天的1只动物,繁殖1个后代,总量为2【第4天】第1天的1只动物又繁殖1只,其他还没繁殖,总量为3【第5天】第1天和第3天出生的动物又繁殖1个后代,其他没有繁殖,总量为5【第n天】.....第1天------1第2天------1第3天------2 = 1 + 1第4天------3 = 1 + 2第5天------5 = 2 + 3第6天------8 = 3 + 5第7天------13 = 5 + 8
这个过程中貌似没发现什么规律,但我们发现从第 3 天开始动物的数量似乎前两天的总和,也就是第 3 天,是第 1 天的动物数量加上第 2 天的动物数量,而第 4 天则是第 2 天和第 3 天的动物数量的和。这样的话我们可以归纳一下,不去直接想 "第 n 天有多少只动物" 而是如下思考:
因此可以总结出递推公式,假设在第 n 天时,第 n-1 天以前繁殖的动物都活着,并且第 n-2 天以前出生的动物会繁殖 1 个后代,设第 n 天的动物总数为 F(n),则有:F(n)=F(n-1)+F(n-2) 其中 n>=3,如下图所示
注意为了让 F(2)=F(1)+F(0) 成立,定义 F(0)=0, 而 F(1) 则依然为 1,因此有如下公式:
我们来验证这个递推公式是否符合递归条件
显然两个条件都符合,说明该通用公式可以在有限的次数内运算完成并达到边界条件得出结果,因此我们可以利用递推公式求出第 11 天的动物的数量:
- F(0) = 0 F(1) = 1 F(2) = F(0) + F(1) = 1 F(3) = F(2) + F(1) = 2 F(4) = F(3) + F(2) = 3 F(5) = F(4) + F(3) = 5 F(6) = F(5) + F(4) = 8 F(7) = F(6) + F(5) = 13 F(8) = F(7) + F(6) = 21 F(9) = F(8) + F(7) = 34 F(10) = F(9) + F(8) = 55 F(11) = F(10) + F(9) = 89也就是说第11天的动物总数为89只
在这个问题中出现的数列就是著名的斐波那契数列,是由数学家斐波那契发现的,由此得名斐波那契数列。
- 0,1,1,2,3,5,8,13,21,34,55,89,…
到此我们也就知道斐波那契数列同样是用递归定义的,前面我们将求解第 n 天的动物数量分解为求第 n-1 天和第 n-2 天以前的动物繁殖后代数量,从把复杂的问题分解为较为简单的同类问题,而不去纠结第 n 天到此有多少只动物的问题,最终发现求解的规律,并通过递推公式求得第 n 天的结果,这个过程再次体现了递归的思维方式。既然斐波那契数列是递归思维的产物,那么也可以通过程序的递归算法来求解,接下来我们就看看如何使用程序中的递归算法来实现斐波那契数列。
实现代码比较简单就不过多分析了,代码如下:
到此我们已对递归分析完了,相信大家对递归已很熟悉了,通过递归的思维方式,在解决某些问题的时候确实使得我们思考的方式得以简化,同时代码也更加精炼,容易阅读。那么既然如此,那是不是什么问题都要用递归来解决呢?难道递归就没有缺点吗?下面我们就来讨论一下递归的不足之处也就是它的效率问题。我们这里以斐波那契数列的实现为例:
- /**
- * 更为简洁的写法
- * @param day
- * @return
- */
- public long fib(int day) {
- return day == 0 ? 0 : (day == 1 || day == 2 ? 1 : fib(day - 1) + fib(day - 2));
- }
这段代码相当精简直观清晰, 但是!如果用这段代码计算 fib(500) 时,我们就泪奔了,它的运行时间也许会让人抓狂呐。我们以 fib(5) 为例,计算过程如下:
?? 从上图可以看出,在计算 Fib(5) 的过程中,Fib(1) 计算了两次、Fib(2) 计算了 3 次,Fib(3) 计算了两次,原本只需要 5 次计算就可以完成的任务却计算了 9 次。更重要的是这个问题随着规模的增加会愈发明显,以至于 Fib(500) 的计算时间已相当恐怖。造成这种困境的原因是,当调用 fib(n-1) 时,还要调用 fib(n-2),也就是说 fib(n-2) 调用了两次,同样的道理,调用 f(n-2) 时 f(n-3) 也调用了两次,而这些多余的调用是完全没有必要的,还可预见的是这种计算方式随着数量的增加,计算量将呈指数级增长,这是一个相当严重的问题。那么如何改良这个计算过程呢?我们重新回顾一下斐波那契数列:
- 0,1,1,2,3,5,8,13,21,34,55,89,…
为了减少函数重复调用提高效率,我们使用迭代的方式来实现斐波那契数列代码如下:
- //BigInteger可以防止数据异常
- //BigInteger 任意大的整数,原则上是,只要你的计算机的内存足够大,可以有无限位的
- // 递推实现方式(迭代的方式效率高,时间复杂度O(n))
- public BigInteger fibonacciN(int n) {
- if (n == 1) {
- return new BigInteger("0");
- }
- //f(0)=0;
- BigInteger n1 = new BigInteger("0");
- //f(1)=1;
- BigInteger n2 = new BigInteger("1");
- //记录最终值f(n)
- BigInteger sn = new BigInteger("0");
- for (int i = 0; i < n - 1; i++) {
- sn = n1.add(n2); //相加
- n1 = n2;
- n2 = sn;
- }
- return sn;
- }
- // 与上述相同的递推实现方式 ,使用long返回值,当n过大会造成数据溢出,计算结果可能是一个未知的负数,因此建议使用BigInteger
- public static long fibonacciNormal(int n) {
- if (n <= 2) {
- return 1;
- }
- long n1 = 1,
- n2 = 1,
- sn = 0;
- for (int i = 0; i < n - 2; i++) {
- sn = n1 + n2;
- n1 = n2;
- n2 = sn;
- }
- return sn;
- }
这样我们就把问题的规模降低到 O(n) 级别了,运行时间也很快,那为什么使用迭代就快,而使用递归就会变得慢呢?我们都知道,递归调用实际上是函数自己在调用自己,而函数的调用开销是很大的(包括空间和时间),而系统要为每次函数调用分配存储空间,提供给函数进行运行。而在函数调用结束后,则需要释放空间,即所谓的弹栈复点。因此函数调用消耗的空间和时间并不是非常乐观的。但难度就不用递归了么?并非如此,当我们在遇到同一个问题时,如果递归解决的(时间和空间)复杂度不明显优于其它解决方案时,此时就不应该使用递归,否则可以使用递归。其实博主想说的是递归虽然有缺点,但在很多复杂的问题上我们使用递归的形式来解释或者求解时问题确实很容易被解释的更清楚,而使用迭代是无法实现的或者难以理解的(如汉诺塔问题,树的遍历等等),此时递归巨大的优势就显示出来了。同时我们更应该记住在相同的问题面前,如果使用递归的效果与迭代的效果相差不了多少,我们更应该倾向于使用迭代,毕竟运行效率上迭代还是相当有优势的。
??ok~,关于递归我们就聊到这里吧,相信已经很清晰了,记住重在理解,切勿陷入递归程序内部去思考!
来源: http://www.bubuko.com/infodetail-1868724.html