数理逻辑17-3.4 递归算法ppt课件

1、数理逻辑Mathematical Logic 第三章 数学推理Chapter 3 Mathematical Reasoning复习n递归定义分两步：n初始步骤初始函数值、初始元素n推导规那么从较小函数值推导当前函数值、从已有元素构造新元素n递归地定义序列n递归地定义函数n递归地定义集合n合式公式n字符串集合、字符串长度的递归定义复习n拉梅定理n用欧几里德算法求gcd(a,b)，其中ab，所运用的除法次数小于或等于b的十进制位数的5倍n斐波那契数nf0=0，f1=1；nfn=fn-1+fn-2，对n=2,3,4,来说3.3 递归算法Recursive Algorithms一、引言n求带有详细的一

2、组输入的问题的解可以归约到带更小的一组输入的一样问题的解n例如gcd(a,b)，其中ban可以归约到求一对更小的整数的最大公约数的问题，即gcd(b mod a,a)n经过一系列这样的归约，直到归约到解是知的某个初始情形为止，就可以求出原问题的解n对求gcd(a,b)来说，不断归约到两个数中较小的一个为0n这样的算法可以处理广泛的问题一、引言n定义：假设一个算法经过把问题归约到带更小的输入的一样问题的实例，来处理原来的问题，那么这个算法称为递归的。n如何构造递归算法从函数的递归定义来求函数的值。n例：给出计算an的递归算法，其中a是非零实数而n是非负整数一、引言q递归算法基于an的递归定义qa

3、01；qan+1=aanq延续地用这个递归定义来减少指数，直到指数是零为止qprocedure powera:非零实数,n:非负整数qif n=0 then power(a,n)=1qelse power(a,n)=apower(a,n-1)一、引言n例：给出求满足a0时，gcd(0,b)=bnprocedure gcd (a,b:非负整数且ab)nif a=0 then gcd(a,b)=bnelse gcd(a,b)=gcd(b mod a,a)一、引言一、引言n例：把线性搜索算法表达成递归过程n为了在序列a1,a2,an里搜索x，在算法的第i步比较x与ain假设x等于ai，那么i是x的位

4、置；n否那么，对x的搜索就归约到少了一个元素的序列即序列ai+1,an里的搜索一、引言一、引言n例：把线性搜索算法表达成递归过程n设：search(i,j,x)是在序列ai,ai+1,aj里搜索x的过程n该过程的输入是个三元组(1,n,x)n假设剩余序列的第一项为哪一项x，或者假设序列只需一项并且它不是x，那么终止n假设x不是第一项而且存在其他的项，那么执行同样的过程，但是搜索序列减少一项删除搜索序列的第一项一、引言n例：把线性搜索算法表达成递归过程nprocedure search (i,j,x)nif ai=x then loc:=inelse if i=j then loc:=0nels

5、e search(i+1,j,x)一、引言n例：构造二分搜索算法的递归方式n假定想在序列a1,a2,an里求出x的位置，为了执行二分搜索，首先比较x与中间项 ，假设x等于这一项，那么算法终止n否那么，把搜索归约到更小的搜索序列n假设x小于原序列的中间项，那么归约到序列的前一半，否那么，归约到后一半(1)/2na一、引言一、引言n例：构造二分搜索算法的递归方式nprocedure binary search (x,i,j)n nif x=am then loc:=mnelse if (xam且iam且jm) thenn binary search (x,m+1,j)nelse loc:=0:()

6、/ 2mij一、引言二、递归与迭代n递归定义把在正整数处的函数值表达成在更小的整数处的函数值n这意味着可以设计递归算法来求出递归地定义的函数在正整数处的值n例：下面的递归算法当输入是正整数n时，给出n！的值qProcedure factorial (n:正整数)qif n=1 thenq factorial(n)=1qelseq factorial(n)=nfactorial(n-1)二、递归与迭代n存在另外一种方式，从阶乘函数的递归定义求它在整数处的值n替代延续地把计算归约到在更小的整数处来求函数的值n从在1处的函数值开场，延续地运用递归定义来求出在更大的整数处的函数值，这样的过程称为迭代二

7、、递归与迭代n为了用迭代求出n!，从1开场，延续地乘以每个小于或等于n的正整数nprocedure iterative factorial (n:正整数)nx:=1nfor i:=1 to nn x=ixnx is n!二、递归与迭代n迭代算法比起运用递归算法来，经常需求较少量的计算n求第n个斐波那契数的递归和迭代算法n递归算法nProcedure fib (n:非负整数)nif n=0 then fib(n)=0nelse if n=1 then fib(n)=1nelse fib(n)=fib(n-1)+fib(n-2)二、递归与迭代n在上述算法中，首先把fn表示成fn-1 +fn-2，然

8、后把这两个斐波那契数都换成两个前面的斐波那契数之和n当f0或f1出现时，就直接换成它的值n在递归的每个阶段，直到获得f1或f0为止，需求求值的斐波那契数的个数都不断翻倍二、递归与迭代n这个算法需求fn+1-1次加法来求出fn二、递归与迭代递归与迭代n迭代算法迭代算法把x初始化成f0=0，把y初始化成f1=1；当经过循环时，把x和y的和赋给辅助变量z；把x赋成y的值把y赋成z的值经过一次循环后，x=f1，y=f0+f1=f2；经过n-1次循环后，x=fn-1，y=fn；因此，用迭代方法求fn仅仅运用了n-1次加法n当求递归定义的函数的值时，递归算法能够比迭代算法需求多得多的计算量n递归算法容易实现而迭代方法不容易实现二、递归与迭代小结n递归算法n递归与迭代n递归定义把在正整数处的函数值表达成在更小的整数处的函数值n迭代是延续地运用递归定义来求出在更大的整数处的函数值n令L(x,y): x爱y，其中x和y的论域都是全世界一切人的集合