第六课 递归程序正确性证明.ppt

第七章程序设计方法学基本理论 ——递归程序的正确性证明;本课的内容; 递归是常用的编程技术，其基本思想是“自己调用自己”。 数学上最常见、最简单的递归问题就是自然数的阶乘。 n=1 n! = 1; n1 n! = n * (n-1)!; 适合用递归方法求解的问题 有一个初始状态 后续的情况可由前面的状态推出 如Fibonacci数列 F1 = F2 = 1; Fn = Fn-1 + Fn-2 (n=3);递归程序概述（2/2）;递归程序的一种模型;递归程序的一种模型;递归程序的例子…;递归程序的例子…;例３ Fibonacci函数 φ(x)?if x=0 then 0 else if x=1 then 1 else φ(x-1) + φ(x-2) 其中，x为非负整数 我们有 φ(0)=0 φ(1)=1 φ(2)= φ(1)+ φ(0)=0+1=1 φ(3)= φ(2)+ φ(1)=1+1=2 φ(4)= φ(3)+ φ(2)=2+1=3 φ(5)= φ(4)+ φ(3)=3+2=5 … ;例４ 计算xy 利用下述公式不难编出相应的递归程序 F(x,y)= xy= F(x,y)=1 若y=0 F(x,y)=(x*x)y/2 若y为偶数 F(x,y)=xy-1*x 若y为奇数 F(x,y)?if y=0 then 1 else if even(y) then F(x*x,y/2) else F(x,y-1)*x 其中，x 为正实数；y为非负整数 例如：F(4,3)=F(4,2)*4=F(16,1)*4 =F(16,0)*64=64 ;例５ McCarthy91函数 M(x)? if x100 then x-10 else M(M(x+11)) 其中，x为任意整数。 对于x=105,有M(105)=95, x=99,其计算过程为 M(99)=M(M(110)) =M(100) =M(M(111))=M(101)=91 可以证明，对于任意整数x M(x)= x-10 x100 91 x=100 值得注意的是，这是具有二重性递归的递归程序 ;(1) 假定应先计算A(1,1)， 然后再计算外层的递归调用 A(1,2) =A(0, A(1,1)) =A(0,A(0,A(1,0))) =A(0,A(0,A(0,1))) = A(0,A(0,2)) = A(0,3) =4;递归计算的计算规则;例７F(x1,x2) ? if x1=0 then 0 else F(0,F(x1,x2)) 其中，(x1,x2) 是任意非负整数对 我们采用两种不同的计算规则来计算F(1,2) 1：规定先计算F的最外层调用 F(1,2)=F(0,F(1,2))=0 (因x1=0) 2：规定先计算F的最内层调用 F(1,2)= F(0,F(1,2)) (因x1?0) = F(0,F(0,F(1,2)))= (因对Ｆ的最内层调用有x1?0) =F(0,F(0,F(0,F(1,2)))) =….. 对于第一种计算规则，F(1,2)的计算过程终止，且F(1,2)=0; 但对第二种计算规则， F(1,2)的计算过程却永不终止，因而F(1,2)无定义。;上述讨论表明： (1)??递归程序可以采用不同的计算规则来进行计算； (2)??采用不同的计算规则来计算递归程序时，对相同的变元，计算过程可能终止，也可能不终止； (3)??如果对于不同的计算规则，相应的递归程序(对相同的自变元)的计算过程都终止，则它们所得的结果一定相同； (4)?? 在(3)的情况下，因为计算过程不同，所以虽然得到的结果相同，但其效率(计算时间和存储量)却可能差别大。;总之，在递归程序的执行过程中，计算规则的选取是很重要的。本章及后面的章节中，将统一规定： 采用”最左，最内”的计算规则，即在计算过程中，总是先计算最内层的F中最左的一个。 例如，在例6中，计算A(1,2)的第一种计算顺序就是按”最左，最内”的计算规则进行的。但在例7中，按”最左，最内”的计算规则去计算F(1,2)却是不终止的，故不能认为F(1,2)＝0. 虽然”最左，最内”的规则未必是最佳的，但现今具有处理递归调用功能 的程序设计语言大都采用这种计算规则。;采用不同计算规则结果不同的例子;简化的LISP程序;原子和表;基本函数