递归程序设计课件

《递归程序设计课件》由会员分享，可在线阅读，更多相关《递归程序设计课件（47页珍藏版）》请在装配图网上搜索。

1、本章内容n递归与循环n递归函数的执行过程n递归函数效率循环与递归n循环程序n用于描述需要重复进行计算n高级语言里，也常见用递归来实现重复的计算。n递归recursion,recursive algorithmn函数或过程调用自身nC语言允许递归，可以在函数内调用自身，常常使程序更简单清晰。1.阶乘和乘幂n例：定义计算整数阶乘的函数n12(n-1)nn本例中，乘的次数依赖于n，计算所需的次数定义时无法确定。n这是一种典型循环情况n计算“次数”依赖某些参数的值。程序long fact1(long n)long fac,i;for(fac=1,i=1;i=n;i+)fac*=i;return fac

2、;阶乘函数的精确定义n是一种递归定义的形式n要解决规模为n的问题，要先解决规模为n-1的子问题，依此类推。n如果高级语言允许递归定义函数，就可以直接翻译为程序。nC允许递归定义n在函数定义内直接或间接地调用被定义函数本身。nnnnn!()!1010写成递归函数long fact(long n)return n=0?1:n*fact(n-1);long fact(long n)if(n=1)return 1;return n*fact(n-1);long fact(1)if(1=1)return 1;return 1*fact(1-1);long fact(2)if(2=1)return 1;r

3、eturn 2*fact(2-1);long fact(3)if(3=1)return 1;return 3*fact(3-1);main()printf(“%d”,fact(3);蓝线：函数调用线路黄线：函数内部执行路线红线：函数执行结束返回主调函数的路线long fact(long n)if(n 1)n1,1,2,3,5,8,13,21,34,65,99,用递归程序实现long fib(int n)return n 2?1:fib(n-1)+fib(n-2);问题分析：这个程序好不好？问题分析：这个程序好不好？一方面，很好！程序与数学定义的关系很清晰，一方面，很好！程序与数学定义的关系很清

4、晰，正确性容易确认，定义易读易理解正确性容易确认，定义易读易理解例fib(5)调用过程fib(5)fib(4)fib(3)fib(3)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)fib(2)fib(1)fib(1)fib(0)存在什么问题？问题n存在大量重复计算，参数越大重复计算越多。n有关系吗？n随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45)n参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年n计算需要时间，复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它

5、不是万能，有些事情“不能”做。计算复杂度n人们发现了许多实际问题，理论上说可用计算机解决（可写出计算它的程序），但对规模大的情况（“大的参数 n”），人类永远等不到计算完成。n这时能说问题解决了吗？n计算中有一大类问题被称为的“难解问题”，其中有许多很实际的问题，如规划、调度、优化等。n解决这些问题，需要理论和实际技术的研究。n另外，对于许多问题的实用的有效算法，有极大的理论价值和实际价值。n计算复杂性，难解问题，“P=NP？”问题。阅读材料：NP问题http:/ problem is assigned to the NP(nondeterministic polynomial time)cl

6、ass if it is solvable in polynomial time by a nondeterministic Turing machine.nA P-problem(whose solution time is bounded by a polynomial)is always also NP.If a problem is known to be NP,and a solution to the problem is somehow known,then demonstrating the correctness of the solution can always be r

7、educed to a single P(polynomial time)verification.If P and NP are not equivalent,then the solution of NP-problems requires(in the worst case)an exhaustive search.nLinear programming,long known to be NP and thought not to be P,was shown to be P by L.Khachian in 1979.It is an important unsolved proble

8、m to determine if all apparently NP problems are actually P.nA problem is said to be NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem.It is much easier to show that a problem is NP than to show that it is NP-hard.A problem which is both NP and NP-har

9、d is called an NP-complete problem.为计算过程计时n统计程序或程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部计时功能。n有关函数在time.h，统计程序时间时程序头部应写n#include n在程序里计时，通常写表达式nclock()/CLOCKS_PER_SECn得到从程序开始到表达式求值时所经历的秒数。确定计算确定计算fib(45)fib(45)所需要的时间的程序所需要的时间的程序#include#include long fib(int n)return n=1?1:fib(n-1)+fib(n-2);int main()double

10、x;x=clock()/CLOCKS_PER_SEC;fib(45);x=clock()/CLOCKS_PER_SEC-x;printf(Timing fib(45):%f.n,x);return 0;Fibonacci数的迭代计算 nFibonacci数的递推计算，易见 n1）f1和f2是1n2）知道fn-2和fn-1连续两个Fibonacci数，就可算出下一个fnn递推计算方式n逐个往后推，可用循环实现递推方案long fib1(int n)long f1=1,f2=1,f3,i;if(n=1)return 1;for(f3=f2+f1,i=2;i n;+i)f1=f2;f2=f3;f3=

11、f1+f2;return f3;做一次递推fnfn-1fn-2程序分析for(f3=f2+f1,i=2;i n;+i)f1=f2;f2=f3;f3=f1+f2;n循环结束时i等于n，这时c的值是fn。n要得到此结论，可设法证明：每次判断 i 的值时f3正是 fi。归纳证明n第一次判断时 i 的值是 2，f3 的值2，正是 fi（且 f1 的值是fi-1，f2 的值是fi-2）n若某次判断时 i 值是 k（小于n），循环体中的语句使f1变成fk-1，f2变成fk，f3变成fk+1。ni 值增 1 使我们又有f1为fi-2，f2变成fi-1，f3变成fi n根据归纳法，每次判断 i 的值时f3正是

12、 fi。如何保证循环的正确执行n循环实现重复性计算，循环体可能执行多次。如何保证对各种数据都能正确完成计算？n循环中变量不断变化。写循环要考虑变量间的关系，保证某些关系在循环中不变：循环的不变关系。n写循环时最重要的就是想清循环中应维持变量间的什么关系才能保证循环结束时变量能处在所需状态。写完循环后应仔细检查是否满足要求。n循环不变关系（循环不变量）是理解循环、写好循环的关键。问题 n本例中用循环的函数比用递归定义的好吗？n新函数在计算时间上有极大优越性。计算时间由循环次数确定。循环体执行次数大致为n。fib(100)只需约100次循环，几乎察觉不到所花费时间。n新函数定义较复杂，有复杂的循环

13、。要理解程序意义，确认函数对任何参数都算出Fibonacci值，需要借助“循环不变关系”的概念和细致分析。注意：这个例子并不是说明递归比循环的效率低。完全可以写出计算fib的同样高效的递归定义的函数最大公约数n求两个整数的最大公约数（greatest common divisor，GCD），写函数 long gcd(long,long)n解法1n从某个数开始，逐个判断当前数是否能同时整除m和n，在这个过程中记录下能同时整除m和n的最大整数。n需要用一个辅助变量k记录当前需要判断的数。n用一个循环实现k顺序取值n初值设为1n每次判断完后增1n直到k大于m和n中其中的一个为止n记下循环过程中出现的

14、新的m和n的公约数，作为新的最大公约数n用变量d表示当前的最大公约数n初值1（是公约数），遇到新的公约数（一定更大）时记入d程序有了d及其初值，k可以从2开始循环。函数定义long gcd(long m,long n)long d=1,k=2;for(;k=m&k=n;k+)if(m%k=0&n%k=0)d=k;return d;参数互素时初值1会留下来，能保证正确计算过程示例mnkk=m&k=nm%k=0&n%k=0d2082是是12是是是是23是是否否24是是是是45是是否否46是是否否47是是否否48是是否否4904特殊情况处理n一些特殊情况需要处理1）m和n都为0需特殊处理。令函数返回

15、值0；2）若m和n中一个为0，gcd是另一个数。函数的返回值正确。也可直接判断处理；3）m、n为负时函数返回1，可能不对。n应在循环前加语句if(m=0&n=0)return 0;if(m=0)return n;if(n=0)return m;if(m 0)m=-m;if(n n?n:m);/把k设为n的较小者 m%k!=0|n%k!=0;k-);/*空循环体*/return k;/*循环结束时k是最大公约数*/过程示例mnkm%k!=0|n%k!=0d2088是是？7是是？6是是？5是是？4否否4两种方式比较n本方法比前一方法简单一些。n两种方法的共同点是重复测试。n这类方法的缺点是效率较低

16、，参数大时循环次数很多。解法2 辗转相除法n求求GCD有著名的欧几里德算法（欧氏算法，有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义：辗转相除法）。最大公约数的递归定义：gcd(,)modgcd(,mod)modm nnmnn mnmn00例n例1ngcd1(70,30)m=70,n=30 m%n 10ngcd(30,10)m=30,n=10 m%n 0n例2ngcd1(65,15)m=65,n=15 m%n 5ngcd1(15,5)m=15,n=5 m%n 0递归程序解决n函数定义与数学定义直接对应long gcd(long m,long n)return m%n=0?n

17、:gcd(n,m%n);假设第二个参数非0，且参数都不小于0。n对欧氏算法的研究保证了本函数能结束，对较大的数计算速度也很快，远远优于顺序检查。加入特殊情况处理long gcd(long m,long n)if(m 0)m=-m;if(n%cn,from,to);void henoi(int n,char from,char to,char by)if(n=1)moveone(from,to);else henoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);moveonemoveone定义为函数是为了方便。函数调用：定义为函数

18、是为了方便。函数调用：henoi(6,a,b,c);henoi(6,a,b,c);北京交通大学计算机与信息技术学院 教师:林友芳hanio(3,a,b,c);hanio(2,a,c,b);moveone(a,b);hanio(2,c,b,a);hanio(2,a,c,b)hanio(1,a,b,c);moveone(a,c);hanio(1,b,c,a);hanio(1,a,b,c)moveone(a,b);hanio(1,b,c,a)moveone(b,c);hanio(2,c,b,a)hanio(1,c,a,b);moveone(c,b);hanio(1,a,b,c);hanio(1,c,a,b)moveone(c,a);hanio(1,a,b,c)moveone(a,b);abc常见方法n设法确认程序对最基本的情况能正常工作n解决了基本情况后再考虑更复杂的情况n设法找出出错的规律性，检查出错时数据经过的执行流，逐步缩小可疑范围n在程序中加入输出语句，检查重要变量的值的变化情况n利用 IDE 的排错功能本章要求n掌握递归的概念n递归函数的编写方法n理解递归函数的效率