递归程序的正确性证明.PPTVIP

本课的内容 1.递归程序概述 2.简化的递归程序模型 3.递归程序的计算规则 4.递归程序的正确性证明 结构归纳法 良序归纳法 递归与迭代程序 在程序设计中，处理重复性的计算常采用的方法是组织迭代循环和采用递归计算的方法，后者特别是在非数值领域中更是如此。 可以证明每个迭代程序原则上总可以转换成与它等价的递归程序；反之不然，并不是每个递归程序都可以转换成与它等价的迭代程序。 就效率而言，递归程序的实现往往比迭代程序耗费更多的时间与存储空间。在具体实现时，又希望尽可能把递归程序转化成等价的迭代程序，从而提高程序的时空效率。 1.递归程序概述 递归是常用的编程技术，其基本思想是“自己调用自己”。 数学上最常见、最简单的递归问题就是自然数的阶乘。 n=1 n! = 1; n1 n! = n * (n-1)!; 适合用递归方法求解的问题 有一个初始状态 后续的情况可由前面的状态推出 如Fibonacci数列 F1 = F2 = 1; Fn = Fn-1 + Fn-2 1.递归程序概述 直接或间接调用自身的程序称为递归程序。 递归实质上也是一种循环结构，它把“较复杂”情况的计算归结为“较简单”情况的计算，一直归结到“最简单”情况的计算为止。 在数值计算领域可以采用递归计算，在非数值领域使用也非常广泛。例如： 河内塔（Hanoi Tower）问题 8皇后问题 骑士巡游问题 此外，递归是人工智能语言Lisp/Prolog等进行问题求解的基本手段。 2.一种简化的递归程序模型 递归程序f(x1,x2,……,xn )可以描述为 f(x1,x2,……,xn ) ≡If p1 then E1 else if p2 then E2 …… else if pm then Em else Em+1 其中pi和Ei中含有f。 递归程序的例子 计算最大公约数GCD(x,y): if x=0 then y else if yx then GCD(y,x) else GCD(x,y-x) GCD(8,4)=GCD(4,8)=GCD(4,4)=GCD(4,0)=GCD(0,4)=4 计算F(x,y) = x y if y=0 then 1 else if even(y) then F(x*x,y/2) else F(x,y-1)*x F(4,3)=F(4,2)*4=F(16,1)*4=F(16,0)*64=1*64=64; 递归程序的例子－多重递归 计算McCarthy91函数M(x) if x100 then x-10 else M(M(x+11)) 例如： M(105)=95 M(99)=M(M(110))=M(100)= M(M(111))=M(101)=91 递归程序－多重递归 Ackermann函数 A(x1,x2 ) If x1=0 then x2+1 else if x2=0 then A(x1-1,1) else A(x1-1,A(x1, x2-1)) 3.递归程序的计算规则 上例说明： 1.递归程序可以采用不同的规则来计算。 2.理论上已经证明，如果同一个递归程序的不同计算规则都终止，那么结果一定也相同。 3.不同的计算过程虽然结果相同，但是时间复杂度和空间复杂度往往不同；实际工作的编译器往往使用“最左最内”规则。（总是先计算最内层的最左的一个） 4.采用不同的计算规则来计算递归程序时，对相同的子变元，计算过程可能终止，也可能不终止。 采用不同计算规则结果不同的例子 F(x1,x2): if x1=0 then 0 else F(0,F(x1,x2)) 先计算最外层调用 F(1,2)=F(0,F(1,2))=0 先计算最内层调用 F(1,2)=F(0,F(1,2))=F(0,F(0,F(1,2)))=…… 简化LISP语言 简化的LISP程序中做如下规定。 １．? 基本的数据结构是原子和表 (1)原子是指字母和数字组成的字符串，且字符之间不允许出现空格，并约定原子必须以字母A,B,C,D,E之一打头，而以其他字母打头的均指变量。 (2)表是指由表元素组成的集合，表元素之间用空格隔开，整个集合用一对方括号［］括起来，表元素可以是原子或其他表。NIL表示空表。 例，①［A B C］——具有３个表元素的