5递推与递归算法2.doc

递推（或迭代）程序设计 递归和迭迭代和递归都是以一种控制语句为基础：迭代使用了循环语句，而递归使用了选择语句。迭代和递归中都包含了循环：迭代显示地使用循环语句；而递归是通过重复的函数调用来实现循环。迭代和递归都包含了终止测试：当循环条件不能满足时，迭代终止；当识别出基本情形时，递归终止。使用计数器控制循环的迭代和循环最终都会到达程序结束处：迭代不断修改计数器，直到计数器达到了使循环条件失败的值；递归不断产生原始问题更加简单的形式，直到达到最基本情形为止。迭代和递归都能够无限制的发生：如果循环条件测试一直为真，那么迭代就会出现无限循环；如果递归步不能按照一种方式每次简化问题收敛于基本情形，那么就会出现无限递归递归的缺点：不断调用函数的机制会导致很高的系统开销，在处理器时间和内存空间上付出昂贵的代价，而良好的软件工程是非常重要的 program ditui1; var x,y,z:longint; i,n:integer; begin write(input n:); read(n); x:=0;y:=1; for i:=1 to n do begin z:=y+x; writeln(x[,i:2,]=,z); x:=y;y:=z; end; end.  例2、用迭代式求y=的值。X由键盘输入。利用下列迭代迭代公式计算 Yn+1= 2/3*Yn+X/(3*Yn*Yn),初始值y0=x,误差要求e=1/10000. 问题分析：反复迭代，循环直至误差符合要求。 源程序： program ditui2; const e=0.0001; var x,y0,y1,y2:real; begin write(input x:); read(x);writeln; y1:=x;y2:=x; repeat y1:=y2; y2:=2/3*y1+x/(3*y1*y1); until abs(y2-y1)e; writeln(x,:X(1/3)=,y2); end. 递归算法深入 递归程序设计使编程语言设计中的一种重要的设计方法，它是许多问题简单化，易于求解。递归的特点：函数或过程调用他自己本身。直接调用成为直接递归，间接调用称为间接递归。 例3、给定n(n1),用递归的方法计算1+2+3+。。。+（n-1）+n 。 源程序： program digui1; var s,t:integer; function fac(n:integer):integer; begin if n=1 then fac:=1 else fac:=fac(n-1)+n; end; begin read(t); s:=fac(t); writeln(s=,s); end. 例4、设有n个数已经按从大到小排好序，编写程序求出给定值x在排序中的位置。 源程序： program digui2; const n=10; var a:array[1..n] of integer; f,r,x,k:integer; procedure search(x,top,bot:integer); var mid:integer; begin if top=bot then begin mid:=(top+bot) div 2 ; if x=a[mid] then writeln(x:5,mid:5,yes) else if xa[mid] then search(x,top,mid+1) else search(x,mid-1,r); end else writeln(x:5,no); end; begin writeln(input 10 datas:); for k:=1 to n do read(a[k]); readln(x); f:=1;r:=n; search(x,f,r); end. 例5、Hanoi（汉诺）塔问题：有n个圆盘，以半径大小（半径都不相同），自下而上套在A柱上，每次只允许移动最上面一个盘子到另外的柱子上去（处A柱外，还有B柱和C柱，开始时着两个柱子上、无盘子），但绝不允许发生柱子上出现大盘子在上，小盘子在下的情况，现要求设计将A柱上的n个盘子移动到C柱上取得方法。编写程序实现。 源程序： program han