Video在线视频

大家好

这一节我们来学习算法

设计方法之递归

递归法是一个非常有趣且实用的算法

我们已经知道

递推是从已知项的值

递推出未知项的值来

而递归

则是从未知项的值递推出已知项的值

再从已知项的值推出未知项的值来

比如

外国友人他如果只懂得一些基本的汉字

他想去查这个字典

如果查第一个字的时候呢他不懂

那么他会去查这个字的解释

直到他看明白之后

会用已知的这个字

再去解释这个未知的词

好的 我们来看另一个例子

有一个家庭 夫妇俩生养了6个孩子

个个都活泼 调皮 可爱

一天 家里来了一客人

见了这一群孩子

难免喜爱和好奇

就问老大

你今年多大了

老大脑子一转

他说 我不告诉你

但是我比老二大2岁

客人就问老二

你今年多大了

老二就学老大 也调皮地说

我也不告诉你

但是我比老三大2岁

如此下去

客人一个一个问下去

孩子们的回答都一样

轮到最小的老六的时候

他诚实地回答

3岁啦

客人倒退回去

马上就可以推出

老五 老四 老三 老二和老大的年龄

在这里

庆幸的是老六“童言无忌”

诚实地告诉了客人

要不然客人难免就会很尴尬

那么

客人他这个推算的过程就是递归

再来看看数学中

有很多递归定义的函数

比如我们熟知的阶乘

这个就是阶乘的定义

n为0的时候 n的阶乘是1

n大于0的时候

n的阶乘是n乘以n减1的阶乘

而在计算学科里

除了利用递归定义基本概念之外

递归还是构造算法的一种基本的方法

如果一个过程

它的算法是直接或者间接调用它自身的

这种过程或者说这种算法就是递归的

递归过程一定要有一个递归的终止条件

也就是说要存在一个“递归出口”

比如说我们刚刚举到那些例子当中

用词典去查生字的例子中

老外至少要有一个基本的词汇量

而在6个孩子的家庭当中

老六说出自己的年龄

这就是递归的终止条件

否则你是无法去推算其他孩子的年龄

在阶乘的递归定义中

0的阶乘是1

这个很明确的定义

就是阶乘递归定义的递归出口

这就是对应的求阶乘的算法

递归与递推是既有区别又有联系的两个概念

递推是从已知的初始条件出发

逐步逐步递推出

直到求到最后一个值

而递归呢 则是从函数本身出发

逐次上溯调用其本身的求解过程

直到这个递归的出口

从这里再往外倒推回来

得到最终的值

你知道吗

一般说来

一个递推算法

总是可以转换成为一个递归算法

此外

有些看起来相当复杂

难以下手的问题

用递归过程来解决

会显得非常的简明

著名的汉诺塔问题

就是用递归来求解的一个经典的例子

汉诺塔问题呢

以前我们做过介绍

就是把A柱子上的64个盘子

借助C柱子

移到B柱子上去

而且每次只能移一个

小盘子要一直放在大盘之上

我们知道

汉诺塔移动的规则是简单的

但是它移动的次数非常多

64个盘子要移动的次数是多少呢

你看

假如

一秒钟移一次

移完这些盘子

需要5845.54亿年以上

而我们的地球目前

也不过是存活了45亿年

那么这么复杂的问题

计算机是如何用递归来求解呢

我们可以想到

要使n个盘子从1柱移到2柱上

无论这个n有多大

你首先都得把n-1个盘子移到3柱上面

然后把第n个盘子从1柱移到2柱

再按同样方式将n减1个盘子

从3柱移到2柱

这样

n个盘子从1柱移到2柱的任务就完成了

至于如何移动那n减1个盘子呢

你可以暂时不管

所以这个程序

你看

就这几句话

非常的简单

这里

过程MoveTower的参数依次表示的是

盘子的个数

起始柱和目的柱

而这个中间的这个

MoveDisk过程的参数

表示从起始柱移动一个盘子到目的柱

这样

移动n个盘子的任务就变成了

两个移动n减1个盘子的任务

外加上一个盘子的移动

如此递归下去

每次从一个柱子到另一个柱子

要移动的盘子数就会减1

直到盘子数为0 这个时候任务就完成了

在完成算法时

我们可以把柱子的这个序号改成变量名

再加上递归终止条件就可以了

这个就是用递归的方法

来求解汉诺塔问题

它显得非常简洁吧

而用非递归方法来求解

算法就会显得比较复杂

有兴趣的话

您可以去找相关资料学习对比一下

正是由于递归算法容易理解

写出来的代码又简洁明了

大家很容易掌握

所以

大多数程序设计语言

都会有递归语言机制

支持递归程序设计

此外

用递归过程来描述算法

不仅非常自然

而且证明算法的正确性

也比相应的非递归形式容易的多

当然

事物总是一分为二的

递归算法有其“长”也有其“短”

不足之处就是算法效率

比非递归算法要低一些

它需要消耗更多的存储空间

和CPU的执行时间

但从“计算思维”的角度来说

递归算法有其巨大的优越性和合理性

因为对于“人”来说

它思路清晰 结构简单 算法明了

对于“机器”来说

执行过程却复杂

消耗的资源要多一些

从某种程度上它解放了我们“程序员”

让人关注抽象层次更高一些的问题

因此

递归是算法设计中最常用的基本技术之一

那么

究竟什么样的问题适合用递归方法来求解呢

通常

满足如下三个条件的问题

适合用递归方法来解决

第一

原始问题可以分解为若干个子问题

大一点的问题可以进一步分解成

小一点的子问题

第二

大问题和小问题具有相同的结构

第三

求解大 小问题的方法是一样的

利用递归方法我们可以做一些非常有意思的事情

我们来看一看这些图形

这些图形都是用递归算法画出来的

你能找出它们的共同特点吗

这一些图形整体上看是极其破碎的

非常不规则的

且十分复杂

又具有无穷的细节

但是在不同的尺度上

图形的规则性又是相同的

比如说这个KOCH曲线

将它局部放大

会发现

它与整个KOCH曲线形状非常相似

这一类的图形

我们把它叫做分形几何图形

我们不妨来看一看

刚刚所说的KOCH曲线

它的生成算法

你能看懂多少呢

这里

并不要求你理解代码

只是想让你直观地看到

首先呢

代码很简洁 不长

第二

从结构上来说

函数koch本身

又调用了koch自身

来生成了4个相似的线段

这就是递归

总之

分形图形具有自相似性

递归性

这些特性

使得人们能通过对部分的认识推及整体

从有限中创造无限

有很积极的意义

好

这一节就到这里

谢谢大家