程序设计基础－张长海－ch10.pptVIP

第十章 递归程序设计 递归程序设计 §10.1 计算n!——递归程序设计 例10-1 编一个函数 factorial 计算阶乘 ｎ! 按过去程序设计思想，该函数应该写成： int factorial ( int n ) { int i,p; p=1; for ( i=1 ; i=n ; i=i+1 ) p=p*i; return p ; } 递归程序设计 例10-3 n 次勒让德多项式 递归程序设计的思想体现在： 用逐步求精原则，先把一个问题分解成若干子问题 这些子问题中有问题的与原始问题具有相同的特征属性，至多不过是某些参数不同，规模比原来小了 此时，就可以对这些子问题实施与原始问题同样的分析算法，直到规模小到问题容易解决或已经解决时为止。 也就是说，若将整个问题的算法设计成一个函数，则解决这个子问题的算法就表现为对相应函数的递归调用. 编写递归程序要注意： 递归程序漂亮、好看、好读、风格优美，但执行效率低。 计算ｎ! 的函数即可以写成循环形式，也可以写成递归形式。但是有些循环程序写成递归很困难。反之，有些递归程序写成循环也很困难，甚至是不可能的。 终结条件。程序一定要能终止，不能无限递归下去。 使用全局量要特别小心。用不好，单元发生冲突，将导致程序出错。 例10-4　汉诺（ Hanoi ）塔游戏 该问题又称世界末日问题。相传，古印度布拉玛婆罗门神庙的憎侣们，当时作一种被称为 Hanoi塔的游戏。该游戏是：在一个平板上，有三根钻石针；在其中一根针上有成塔型落放的大小不等的64片金片；要求把这64片金片全部移到另一根钻石针上。移动规则是： 每次只允许移动一片金片； 移动过程中的任何时刻，都不允许有较大的金片放在较小的金片的上面； 移动过程中，三根钻石针都可以利用，但是金片不许放在除钻石针以外的任何地方。 不论白天黑夜都有一个憎侣在移动。据说当64片金片全部从一根钻石针移到另一根钻石针上那天，就是世界的末日。到那时他们的虔诚信徒可以升天，而其他人则要下地狱。 §10.2 间接递归 前边讲的递归程序，都是在函数本身的函数体内调用自己。 而递归的动态含义是在调用函数进入函数后，没有退出之前，又再一次调用本函数。 可能存在如图所示情况，这显然也是进入P后，没退出P之前又再一次调用P ，这种情况称“间接递归”。 相应前边讲的“在P中直接调用P”称“直接递归”。 例 10-5 编程序，从终端读入表达式，计算表达式的值。表达式遵守先乘除后加减的运算规则，并且允许有括号。它的语法是： E ： T+E 或者 T-E 或者 T T ： F*T 或者 F/T 或者 F F ： 数字 或者 (E) 解：把每个语法单位的处理编成一个函数，全局量w保存当前字符，构造算法如下 §10.3 递归程序执行过程 例 10-7 从前 n 个自然数 1 , 2 , 3 , ... , n 中取 r 个数作组合，打印全部所有组合。 例如，n=5 、r=3 ，便有如下10种组合。 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 本章小结 递归程序设计 间接递归 递归程序执行过程 与 E 同理，从 T 的文法 T → F*T ▌F/T ▌F 看出T 由 F 组成； F 开始，后边跟以 * 、/ 号，后边再跟以 T 组成 我们先处理 F ；然后根据 F 后继符决定下一步处理。 若结束，则 F 值即为 T 的值； 若 F 后继符号是运算符号，则记录运算符号； 再处理 T ；最后再根据记录的运算符号进行计算。 从而得到如下 PAD 。 t(*vt) 返回 f(u1) w == * / w1=w t(u2) w1==* *vt=u1*u2 *vt=u1/u2 *vt=u1 考虑 F 的处理，根据 F 的文法： F → ＜数字＞▌(E) F 由数字组成；或者由括号括起来的 E 组成。得到如下算法PAD 。 最后，主程序就是简单调用 E 函数。PAD如下。 f(*vf) 返回 w=( *vf=w e(vf) 开始 结束 印 v e(v) 主函数在开始应该首先读入一个字符； E 的处理函数，也应该加上读入字符部分； 与 E 一样，相应 T 的处理函数，也应该加上读入字符部分。 最后，F 的处理