第12章 非递归化 本章主要介绍下列内容（教材第四章） 1. 问题引入（递归问题） 2. 栈 3. 递归过程的改写 4. 小结 课时分配：第1、2节讲授三个学时，第3、4节讲授三个学时，上机三小时 重点、难点：递归过程的改写 第一节 问题引入 一、使用递归的好处 使所描述的算法或程序简洁明了。 二、为什么要将递归算法非递归化？ 1．有些语言不支持递归功能。 2．当问题规模太大时，递归算法所耗时间和空间都较非递归算法多。 3．递归所使用的空间主要由编译程序自动分配堆栈，空间较小；非递归所使用的空间 可由程序自行在堆动态空间中申请，容量大。 三、为什么教材主要讨论直接递归的非递归化问题？ 因为间接递归大多可转化成直接递归。例如： Var a,b,n;integer; Procedure P2(Var x:integer);forword; Procedure P1(y:integer); begin y:=y*2+10;b:=y Div 30;P2(y); end Procedure P2; Begin If x<400 then begin n:=n+1;P1(x) end End; Begin Write(‘input a=’);readln（a）;n:=0;P2(a); Writeln(‘N=’,n:3,‘,B=’,b:4) End. 运行： Input a=21 N=4,B=16 Input a=-156 N=8,B=938 以上两过程即是间接递归调用，可将其合为如下的直接递归调用过程。 Procedure P2(Var d:integer); Var y:integer; Begin if x<400 then Begin n:=n+1; y:=x;y:=y*2+10; 可优化成y:=x*2+10; b:=y Div 30; P2(y) End End; 还可进一步优化成： Procedure P2(Var d:integer); begin if x<400 then begin n:=n+1;x:=x*2+10;b:=x Div 30;P2(x);end end; 四、递归与循环可以相互转换，见P89。 ①尾部递归 五、顺序搜索的递归和非递归算法，见P89。 ②函数 六、递归问题（略讲） 第二节 栈 栈是改写递归算法和理解递归算法的工具。理解实例可介绍《数据结构》教材中河内塔 部分补充页码！ 一、尾递归及其非递归化（见P93） 变成非递归时可不用栈。 1．定义 2．方法 二、非尾递归的非递归化 要用栈这种数据结构来实现，每一个需保存的变量设置一个栈。局部变量、值参量和返 回点都需栈，但全局变量和变参不要栈。 1．关键点——递归过程的开始点、结束点和返回点。 2．以非尾递归算法Tower的非递归化为例说明一般步骤和方法。见P95-P97 自学 第三节 递归过程的改写 该节进一步总结非递归化方法，请学生自学方法。 一、Tower3在Tower2基础上减少了四个局部变量。P99 二、99-100页Quick算法的非递归化请同学自学。 三、Permu的非递归化要重点介绍——见P100-101。 这是递归调用语句出现在循环体中的情形，这种情况要将循环语句变形成if+goto形式 后再非递归化。 四、哪些量要进栈保存？ 有关原则见P102。 第四节 小 结 一、递归问题的非递归化步骤 二、递归函数转化成过程后再非递归化 三、间接递归转化成直接递归后再非递归化 四、尾递归一般用While或repeat实现非递归化，其它情况用if+goto实现。 五、一个补充实例： 写出递归函数 ? ? ? ? ?? ? ≥ <+= 2)4(*2 21)( nnfnf nnnf 的非递归求值过程。 原递归算法之变形： Procedure exmp(n,Var f); Var u1,u2:integer; begin 0: if n<2 then [f:=n+1;goto 3]; exmp(n Div 2,u1); 1: exmp(n Div 4,u2) exmp(n Div 4,f); 2: 2: f:=u1*u2 f:=u1*f; 3: end; 实际上，将非递归过程还原成函数非常容易。 非递归算法： Procedure exmp(n,Var f); Var r:记录(rd,Pn,u1);s:栈(r型记录数组) begin 初始化栈S; 0:if n<2 then [f:=n+1;Goto 3]; r.rd:=1;r.Pn:=n;Push(s,r);n:=n Div 2;Goto 0; 1:n:=Top(s,Pn);Top(s,u1):=f;r.rd:=2 ? Push(s,r);n:=top(s,Pn) Div 4;Goto 0; 2:pop(s);f:=Top(s,u1)&f;pop(s); 3:if not empty(s) then Goto Top(s,rd) end;{最后结果存在f中} 在黑板上举n=12为例进行演示！ 另一个更简单方法由95级陈强和96级彭磊给出： int f(int n) {int f1; 栈s置空；n进栈;f1:=1; while(s) {pop(s,n);if(n==1)f1=f1+f1; if(n>1){push(s,n/2);push(s,n/4);} } return f1; } 或： int ff(int n) {int I,f[n]; f[0]=1;f[1]=2; for(i=2;i<=n;i++)f[i]=f[i/2]*f[i/4]; return f[n];} 这是纯递推办法，虽效率低，但直观易编程！ 以FeiboNacci数列第n项的求法引入这个算法： ①根据通项公式计算第n项之值； ②直接递推求解 由此看来，函数的非递归化因为是求值，比过程的非递归化更简单。 ③递归方程： ? ? ? ??? ? > = = = 1* 12 01 42 nff n n f nn n 的解法见补充材料（学报待发）。 关于 P 与 NP理论简介，可根据时间或学生实际略讲或不讲。 一、问题分类 1．无法写出算法的问题——难题 2．有以多项式为界的算法存在的问题——P类问题 3．介于前两类之间的问题——存在指数阶算法，但不知道是否存在多项式算法（NP问 题） 二、概述 1．问题 2．问题实例 3．解决某问题的算法 4．问题实例的大小 5．将问题实例转化（映射）成字符串进行研究 6．两种难的问题 7．研究“难”解问题的两种方法 （1）证明一个问题是“难”的； （2）研究难问题之间的关系，这有助于算法设计，主要方法是“归约”。 本章其它部分从略。