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