第三节递归过程的改写 该节进一步总结非递归化方法,请学生自学方法 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 Û