递归程序设计

递归程序设计第1页，共49页，2023年，2月20日，星期四本章内容递归与循环递归函数的执行过程递归函数效率第2页，共49页，2023年，2月20日，星期四循环与递归循环程序用于描述需要重复进行计算高级语言里，也常见用递归来实现重复的计算。递归—recursion,recursivealgorithm函数或过程调用自身C语言允许递归，可以在函数内调用自身，常常使程序更简单清晰。第3页，共49页，2023年，2月20日，星期四1.阶乘和乘幂例：定义计算整数阶乘的函数1×2×…×(n-1)×n本例中，乘的次数依赖于n，计算所需的次数定义时无法确定。这是一种典型循环情况计算“次数”依赖某些参数的值。第4页，共49页，2023年，2月20日，星期四程序longfact1(longn){longfac,i;for(fac=1,i=1;i<=n;i++)fac*=i;returnfac;}第5页，共49页，2023年，2月20日，星期四阶乘函数的精确定义是一种递归定义的形式要解决规模为n的问题，要先解决规模为n-1的子问题，依此类推。如果高级语言允许递归定义函数，就可以直接翻译为程序。C允许递归定义在函数定义内直接或间接地调用被定义函数本身。第6页，共49页，2023年，2月20日，星期四写成递归函数longfact(longn){returnn==0?1:n*fact(n-1);}longfact(longn){if(n<=1)return1;returnn*fact(n-1);}第7页，共49页，2023年，2月20日，星期四longfact(1){if(1<=1)return1;return1*fact(1-1);}longfact(2){if(2<=1)return1;return2*fact(2-1);}longfact(3){if(3<=1)return1;return3*fact(3-1);}main(){printf(“%d”,fact(3));}蓝线：函数调用线路黄线：函数内部执行路线红线：函数执行结束返回主调函数的路线longfact(longn){if(n<=1)return1;returnn*fact(n-1);}第8页，共49页，2023年，2月20日，星期四递归与计算过程包含递归的程序产生的计算过程和性质更复杂，能完成很复杂的工作。递归调用只有一个调用表达式或语句，但是可能要许多步才能完成。实际参数的不同，会实际产生的递归调用次数（步数）也会有很大的不同。递归程序理解的理解比较困难递归的函数定义需要有条件语句去控制递归过程的最终结束直接给出结果的时候，递归结束；把对较复杂情况的计算归结为对更简单情况的计算，需要进行递归处理。第9页，共49页，2023年，2月20日，星期四递归和循环基本运算、关系判断、条件表达式，加函数定义和递归定义构成了一个（理论上）“足够强的”的程序语言。循环程序可以改成递归实现递归程序也可以改成循环实现第10页，共49页，2023年，2月20日，星期四。2.Fibonacci序列计算与时间第11页，共49页，2023年，2月20日，星期四定义Fibonacci（斐波那契）序列的递归定义F0=1,F1=1Fn=Fn-1+Fn-2(n>1)1,1,2,3,5,8,13,21,34,65,99,…第12页，共49页，2023年，2月20日，星期四用递归程序实现longfib(intn){returnn<2?1:fib(n-1)+fib(n-2);}问题分析：这个程序好不好？一方面，很好！程序与数学定义的关系很清晰，正确性容易确认，定义易读易理解第13页，共49页，2023年，2月20日，星期四例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)存在什么问题？第14页，共49页，2023年，2月20日，星期四问题存在大量重复计算，参数越大重复计算越多。有关系吗？随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45)参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年计算需要时间，复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它不是万能，有些事情“不能”做。第15页，共49页，2023年，2月20日，星期四计算复杂度人们发现了许多实际问题，理论上说可用计算机解决（可写出计算它的程序），但对规模大的情况（“大的参数n”），人类永远等不到计算完成。这时能说问题解决了吗？计算中有一大类问题被称为的“难解问题”，其中有许多很实际的问题，如规划、调度、优化等。解决这些问题，需要理论和实际技术的研究。另外，对于许多问题的实用的有效算法，有极大的理论价值和实际价值。计算复杂性，难解问题，“P=NP？”问题。第16页，共49页，2023年，2月20日，星期四阅读材料：NP问题

/NP-Problem.htmlAproblemisassignedtotheNP(nondeterministicpolynomialtime)classifitissolvableinpolynomialtimebyanondeterministicTuringmachine.AP-problem(whosesolutiontimeisboundedbyapolynomial)isalwaysalsoNP.IfaproblemisknowntobeNP,andasolutiontotheproblemissomehowknown,thendemonstratingthecorrectnessofthesolutioncanalwaysbereducedtoasingleP(polynomialtime)verification.IfPandNParenotequivalent,thenthesolutionofNP-problemsrequires(intheworstcase)anexhaustivesearch.Linearprogramming,longknowntobeNPandthoughtnottobeP,wasshowntobePbyL.

Khachianin1979.ItisanimportantunsolvedproblemtodetermineifallapparentlyNPproblemsareactuallyP.AproblemissaidtobeNP-hardifanalgorithmforsolvingitcanbetranslatedintooneforsolvinganyotherNP-problem.ItismucheasiertoshowthataproblemisNPthantoshowthatitisNP-hard.AproblemwhichisbothNPandNP-hardiscalledanNP-completeproblem.第17页，共49页，2023年，2月20日，星期四为计算过程计时统计程序或程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部计时功能。有关函数在time.h，统计程序时间时程序头部应写#include<time.h>在程序里计时，通常写表达式clock()/CLOCKS_PER_SEC得到从程序开始到表达式求值时所经历的秒数。第18页，共49页，2023年，2月20日，星期四确定计算fib(45)所需要的时间的程序#include<stdio.h>#include<time.h>longfib(intn){returnn<=1?1:fib(n-1)+fib(n-2);}intmain(){doublex;

x=clock()/CLOCKS_PER_SEC;fib(45);

x=clock()/CLOCKS_PER_SEC-x;printf("Timingfib(45):%f.\n",x);return0;}第19页，共49页，2023年，2月20日，星期四Fibonacci数的迭代计算Fibonacci数的递推计算，易见1）f1和f2是12）知道fn-2和fn-1连续两个Fibonacci数，就可算出下一个fn递推计算方式逐个往后推，可用循环实现第20页，共49页，2023年，2月20日，星期四递推方案longfib1(intn){longf1=1,f2=1,f3,i;if(n<=1)return1;for(f3=f2+f1,i=2;i<n;++i){f1=f2; f2=f3;f3=f1+f2;}returnf3;}做一次递推fnfn-1fn-2第21页，共49页，2023年，2月20日，星期四程序分析for(f3=f2+f1,i=2;i<n;++i){f1=f2;f2=f3;f3=f1+f2;}循环结束时i等于n，这时c的值是fn。要得到此结论，可设法证明：每次判断i的值时f3正是fi。第22页，共49页，2023年，2月20日，星期四归纳证明第一次判断时i的值是2，f3的值2，正是fi（且f1的值是fi-1

，f2的值是fi-2）若某次判断时i值是k（小于n），循环体中的语句使f1变成fk-1

，f2变成fk

，f3变成fk+1

。i值增1使我们又有f1为fi-2

，f2变成fi-1

，f3变成fi

根据归纳法，每次判断i的值时f3正是fi。第23页，共49页，2023年，2月20日，星期四如何保证循环的正确执行循环实现重复性计算，循环体可能执行多次。如何保证对各种数据都能正确完成计算？循环中变量不断变化。写循环要考虑变量间的关系，保证某些关系在循环中不变：循环的不变关系。写循环时最重要的就是想清循环中应维持变量间的什么关系才能保证循环结束时变量能处在所需状态。写完循环后应仔细检查是否满足要求。循环不变关系（循环不变量）是理解循环、写好循环的关键。第24页，共49页，2023年，2月20日，星期四问题本例中用循环的函数比用递归定义的好吗？新函数在计算时间上有极大优越性。计算时间由循环次数确定。循环体执行次数大致为n。fib(100)只需约100次循环，几乎察觉不到所花费时间。新函数定义较复杂，有复杂的循环。要理解程序意义，确认函数对任何参数都算出Fibonacci值，需要借助“循环不变关系”的概念和细致分析。注意：这个例子并不是说明递归比循环的效率低。完全可以写出计算fib的同样高效的递归定义的函数第25页，共49页，2023年，2月20日，星期四最大公约数求两个整数的最大公约数（greatestcommondivisor，GCD），写函数longgcd(long,long)解法1从某个数开始，逐个判断当前数是否能同时整除m和n，在这个过程中记录下能同时整除m和n的最大整数。需要用一个辅助变量k记录当前需要判断的数。用一个循环实现k顺序取值初值设为1每次判断完后增1直到k大于m和n中其中的一个为止记下循环过程中出现的新的m和n的公约数，作为新的最大公约数用变量d表示当前的最大公约数初值1（是公约数），遇到新的公约数（一定更大）时记入d第26页，共49页，2023年，2月20日，星期四程序有了d及其初值，k可以从2开始循环。函数定义longgcd(longm,longn){longd=1,k=2;for(;k<=m&&k<=n;k++)if(m%k==0&&n%k==0)d=k;returnd;}参数互素时初值1会留下来，能保证正确第27页，共49页，2023年，2月20日，星期四计算过程示例mnkk<=m&&k<=nm%k==0&&n%k==0d2082是12是是23是否24是是45是否46是否47是否48是否4904第28页，共49页，2023年，2月20日，星期四特殊情况处理一些特殊情况需要处理1）m和n都为0需特殊处理。令函数返回值0；2）若m和n中一个为0，gcd是另一个数。函数的返回值正确。也可直接判断处理；3）m、n为负时函数返回1，可能不对。应在循环前加语句if(m==0&&n==0)return0;if(m==0)returnn;if(n==0)returnm;if(m<0)m=-m;if(n<0)n=-n;第29页，共49页，2023年，2月20日，星期四可能方式2换个思路令k从某个恰当的大数开始递减，找到的第一个公约数就是最大公约数。k初值可取m和n中小的一个。结束条件k值达到1或找到了公约数。1总是公约数。程序主要部分可写为：for(k=(m>n?n:m);//把k设为n的较小者

m%k!=0||n%k!=0;k--) ;/*空循环体*/returnk;/*循环结束时k是最大公约数*/第30页，共49页，2023年，2月20日，星期四过程示例mnkm%k!=0||n%k!=0d2088是？7是？6是？5是？4否4第31页，共49页，2023年，2月20日，星期四两种方式比较本方法比前一方法简单一些。两种方法的共同点是重复测试。这类方法的缺点是效率较低，参数大时循环次数很多。第32页，共49页，2023年，2月20日，星期四解法2辗转相除法求GCD有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义：第33页，共49页，2023年，2月20日，星期四例例1gcd1(70,30)m=70,n=30m%n10gcd(30,10)m=30,n=10m%n0例2gcd1(65,15)m=65,n=15m%n5gcd1(15,5)m=15,n=5m%n0第34页，共49页，2023年，2月20日，星期四递归程序解决函数定义与数学定义直接对应

longgcd(longm,longn) { returnm%n==0?n:gcd(n,m%n); }

假设第二个参数非0，且参数都不小于0。对欧氏算法的研究保证了本函数能结束，对较大的数计算速度也很快，远远优于顺序检查。第35页，共49页，2023年，2月20日，星期四加入特殊情况处理longgcd(longm,longn){

if(m<0) m=-m;if(n<0) n=-n;returnn==0?m:gcd(m,n);}第36页，共49页，2023年，2月20日，星期四循环方法辗转相除就是反复求余数，也是重复性工作，可可用循环结构实现。出发点m和n；循环判断m%n是否为0若是则n为结果；否则更新变量：令m取n的原值，n取m%n的原值。为正确更新需用辅助变量r，正确的更新序列：r=m%n;m=n;n=r;第37页，共49页，2023年，2月20日，星期四非递归函数定义longgcd2(longm,longn){longr;if(n==0) returnm;for(r=m%n;r!=0;r=m%n){ m=n;n=r;}returnn;}参数是局部变量，可在函数体里使用和修改。第38页，共49页，2023年，2月20日，星期四河内塔（梵塔问题）第39页，共49页，2023年，2月20日，星期四河内塔（hanoi塔，梵塔）问题问题出自古印度（一说西藏）某神庙有三根细柱，64个大小不等、中心有孔的金盘套在柱上，构成梵塔。僧侣日夜不息地将圆盘从一柱移到另一柱。规则每次只移一个盘，大盘不能放到小盘上。开始时圆盘从大到小套在一根柱上，据说所有圆盘都搬到另一根柱时世界就要毁灭。第40页，共49页，2023年，2月20日，星期四图示第41页，共49页，2023年，2月20日，星期四要求要求写程序模拟搬圆盘过程，打印出搬动指令序列。为方便，分别将三根圆柱命名为a、b和c，假定开始时所有圆盘都在a上，要求最终搬到b。第42页，共49页，2023年，2月20日，星期四问题分析初看问题似乎没规律。求解的关键在于看到问题的“递归性质”。搬64个盘的问题可归结为两次搬63个盘。搬n个圆盘的问题可以归结为搬n-1个圆盘，把n个盘从柱A搬到柱B的工作可以如下完成从柱A借助柱B将n-1个圆盘搬到柱C；将最大圆盘从柱A搬到柱B；从柱3借助柱A将n-1个圆盘搬到柱B；第43页，共49页，2023年，2月20日，星期四从柱A借助柱B将3个圆盘搬到柱CABCABCABCACB从柱A将最大的圆盘移动B柱从柱C借助柱A将3个圆盘搬到柱B第44页，共49页，2023年，2月20日，星期四voidmoveone(charfrom,charto){printf("%c->%c\n",from,to);}

voidhenoi(intn,charfrom,charto,charby){if(n==1) moveone(from,to);else{henoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);}}moveone定义为函数是为了方便。函数调用：henoi(6,'a','b','c');第45