第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