3.4栈与递归的实现在线视频

同学们大家好

今天我们讨论一下栈与递归的实现

我们先讨论递归程序设计的问题

从程序实现的角度来说

说一个函数是递归函数

就是说在这个函数内部出现直接或者间接对自身的调用

例如，引例中的求阶乘函数fact(n)

函数的目的是求参数n的阶乘

在fact内部出现了对函数fact的直接调用n*fact(n-1)

那么fact函数就是一个递归函数

请大家考虑一个问题

为什么要在一个函数内部对自身进行调用？

请大家带着这个问题来学习下面的内容

分解问题是我们常用的解决复杂问题的方法

当一个问题比较复杂的时候

通过问题分解

可以把它分解为一些子问题

通过逐个解决这些子问题

利用子问题的结果

最终达成对原问题的求解

这是一种控制问题复杂性的有效策略

在各种领域都有广泛的应用

递归的本质也是一种问题分解的策略

我们注意到

有的问题之所以我们觉得比较复杂

是因为问题规模比较大的时候

该问题不太好解决

我们以求阶乘为例

假设原问题是求10的阶乘

它的解不是我们能立刻说得出来的

问题不太好解决

在这，我们尝试对问题进行递归分解

根据阶乘的定义

我们可以把求10的阶乘

分解为先求9的阶乘，求得9的阶乘后

再乘以10，就求得了10的阶乘

求10的阶乘和求9的阶乘都是求阶乘的问题

但求9的阶乘其问题的规模缩小了

9的阶乘也不是能直接得出的

继续进行分解

把求9的阶乘

分解为先求8的阶乘

求得8的阶乘后

再乘以9，就求得了9的阶乘

8个阶乘同样不容易直接求得

我们可以把这个分解过程继续下去

求阶乘的问题规模会越来越小

最终分解成求1的阶乘

1的阶乘实际上是可以直接获得的

它就是1。我们通过递归分解

逐渐把问题分解为同类型的规模缩小的子问题

当问题规模足够小的时候

问题也就不是什么复杂问题了

往往可以直接求解

当求得了1的阶乘以后

就可以递归返回

把1阶乘的结果乘以2

可以得到2的阶乘

继续返回

用2阶乘的结果乘以3

可以获得3的阶乘

一直到通过9的阶乘结果乘以10

获得10的阶乘

这是通过逐渐合并子问题的解得到原问题解的过程

如果对问题进行了适当的递归分解

那么写递归程序就变得非常简单了

我们来看一下求阶乘这个函数

参数是n，就是说要调用fact求n的阶乘

如果n是负数，无法求阶乘

退出

否则如果n小于等于1

可以直接返回结果

return（1）

再否则

其它情况

我们就进行递归分解

把求n的阶乘问题

通过递归调用fact（n-1）

调用自身求出求n-1的阶乘

调用返回后n-1阶乘的结果乘以n

可以获得n的阶乘了

当然这样的递归调用有多层

具体多少层要看n的大小

上面例子中求10的阶乘

其递归层数有10层

求阶乘函数中只有一次对自身的调用

这样的递归称为单递归

很容易可以用循环实现

不需要写成递归程序

现在，我们可以考虑刚才的问题了

为什么要在一个函数内部对自身进行调用？

在递归程序中之所以调用自身

是因为经过问题分解以后

子问题和原问题是同类型的

只不过它的规模缩小

调用自身的目的是解决

同样的，规模缩小的子问题

总结一下递归的本质呢

就是把问题分解为同类型的

规模缩小的子问题

我们在做递归程序设计的时候

先不要盲目的去写程序

而是应该首先清晰的进行问题分解

问题分解完成了

写递归程序是很简单的事情

我们再看一个递归程序的例子

河内塔问题

先对河内塔问题进行一个简单的陈述

有三根针，x，y和z

在x上有n个圆盘

圆盘大小都不相同

靠上部的小，靠下部的大

我们要解决的问题是

将x上的n个圆盘

移动到z上

不过移动的时候呢

要遵守三条规则

一是，每次只能移动一个圆盘

二是，圆盘可以插在任意塔座上

三是，在移动的任何时刻

不能出现大盘压小盘的情况

这个问题是一个时间复杂度非常高的问题

我们把原问题做一个叫形式化的表示

H n x y z，意思是把x上的n个圆盘

以y为辅助，最终搬到z上

我们以三个圆盘为示例

为了解决这个较复杂的问题

我们把它分解为三个子问题

第1个子问题h(n-1,x, z, y)；

意思是把x上面的n-1个圆盘

以z为辅助搬到y上

如果这个问题解决了

那么应该是x上部的n-1个圆盘已经搬到了

仅仅留下最大的一个圆盘在x上

如图1所示

第2个子问题move(x, n号盘，y)

比较简单，就是把x上最大的n号盘

直接搬到z上，这个问题解决后的情形如图2所示

第3个子问题h(n-1,y, x, z)；

意思是我们需要把第1个子问题中移动到y上的n-1个圆盘

以x为辅助，搬到z上

这个子问题解决了

情形如图③所示，我们看到原问题已经得到了解决

通过这个分解过程，我们可以看到

N规模的河内塔问题

被我们分解为两个n-1规模的河内塔问题

加上一次一个圆盘的移动

这三个子问题解决了

原问题也就解决了

两个n-1规模的问题

和原问题类型相同

问题的规模都缩减了1

有了这样的问题分解

设计河内塔问题的递归程序就很容易了

下面我们看一下程序

河内塔问题的函数涉及到4个参数

4个参数n x y z的含义

刚才实际上已经看到了

就是x上的n个圆盘

以y为辅助，移动到z上

在函数中，如果n=1

就是说x只有一个圆盘

那么我们直接把这个圆盘从x搬到y就可以了

否则，当问题规模大于1的时候

我们则进行问题分解

通过刚才关于问题分解的讨论

我们知道，可以把n更规模的问题

分解成两个n-1规模的问题，加一次搬动

函数中，首先通过递归调用hanoi(n-1, x, z, y);

把x上的n-1个圆盘

以z为辅助，搬到y上

这个子问题解决以后

把x上最大一个圆盘

直接搬到z上

最后，把搬到y上的n-1个圆盘

以x为辅助，搬到y上

完成原问题的要求

教材中还讨论了系统如何通过栈支持递归调用的实现

同学们自己下去认真学习一下

同学们，这节课我们就讨论到这儿

下节课再见