递归算法解题的一般思路

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:46:24

在一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清楚，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。

利用递归算法解题，首先要对问题的以下三个方面进行分析：

一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。

二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。

三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。

把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：

if 边界条件 1 成立 then

赋予边界值 1

【 elseif 边界条件 2 成立 then

赋予边界值 2

┇ 】

else

调用解决问题的通式

endif

例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。

分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很轻易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：

P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。

接下来按照上面介绍的一般格式定义递归子程序。

function Pnx(n as integer)

if n ＝ 0 then

Pnx ＝ 1

elseif n ＝ 1 then

Pnx ＝ x

else

Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n

endif

end function

例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；

(2) 盘子只许在三根针上存放；

(3) 永远不许大盘压小盘。

梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。

要求设计一个程序输出盘子的移动过程。

分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。

当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：

(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；

(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；

(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很轻易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。假如再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。

这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：

hanoi(n － 1,s,o,i)

move(s,n,o)

hanoi(n － 1,i,s,o)

参考程序如下：

declare sub hanoi(n,s,i,o)

declare sub move(s,n,o)

input "How many disks?",n

s ＝ 1

i ＝ 2

o ＝ 3

call hanoi(n,s,i,o)

end

sub hanoi(n,s,i,o)

rem 递归子程序

if n ＝ 1 then

call move(s,1,o)

else

call hanoi(n － 1,s,o,i)

call move(s,n,o)

call hanoi(n － 1,i,s,o)

endif

end sub

sub move(s,n,o)

print "move disk";n;

print "from";s;"to";o

end sub

上一篇：{应用}穷举算法解题的一般思路 人气:7159
下一篇：{应用}迭代算法解题的一般思路 人气:4784

C语言程序设计视频教程