1. 目的1掌握递归和递推的概念能够利用递归思想编写程序。2能辨析递归和递推技术的优劣。3能利用递归和递推技术解决问题。2. 任务及步骤2.1 递归与递推的开销对比递归与递推的代码框架如下#includeiostream#includectimeusingnamespacestd;doublerecursion(intn)//递归求阶乘{}doubleiteration(intn)//递推求阶乘{}intmain(){intN10,start,finish;doubleresult;startclock();for(inti0;i100000;i)//重复执行100000次确保感知到执行时间resultrecursion(N);finishclock();cout递归结果resultendl用时finish-startmsendl;startclock();for(inti0;i100000;i)//重复执行100000次确保感知到执行时间resultiteration(N);finishclock();cout递推结果resultendl用时finish-startmsendl;return0;}任务1递归与递推求 n 的阶乘① 阶乘的递归定义n!n ×(n-1)!② 阶乘的递推定义n!1×2×3× …… × n源程序代码及运行#includeiostream#includectimeusingnamespacestd;doublerecursion(intn)//递归求阶乘{doubleresult;if(n0)return1;elsereturnn*recursion(n-1);}doubleiteration(intn)//递推求阶乘{doubleres1;for(inti1;in;i){res*i;}returnres;}intmain(){intN10,start,finish;doubleresult;startclock();for(inti0;i100000;i)//重复执行100000次确保感知到执行时间resultrecursion(N);finishclock();cout递归结果resultendl用时finish-startmsendl;startclock();for(inti0;i100000;i)//重复执行100000次确保感知到执行时间resultiteration(N);finishclock();cout递推结果resultendl用时finish-startmsendl;return0;}运行结果截图任务2比较递归法和递推法在解决相同规模问题时执行时间上的优劣统计算法的执行时间可利用 Excel 表格绘制折线图进行比较。2.2 慎重采用递归求解的问题任务3递归与递推求斐波那契数列的第 n 项③ 斐波那契数列的递归定义f(n)f(n-1)f(n-2)其中f(0)f(1)1④ 斐波那契数列的递推实现febo(n)//迭代求斐波那契数列返回第n项{a1,b1;if(n2)return1;fori2to n{numab;ab;bnum;}returnnum;}源程序代码及运行结果截图#includeiostream#includectimeusingnamespacestd;doublerecursion(intn)//递归求斐波那契数列{if(n0||n1)return1;elsereturnrecursion(n-1)recursion(n-2);}doubleiteration(intn)//递推求斐波那契数列{inta1,b1,num;if(n2)return1;for(inti2;in;i){numab;ab;bnum;}returnnum;}intmain(){intN5,start,finish;doubleresult;startclock();resultrecursion(N);finishclock();cout递归结果resultendl用时finish-startmsendl;startclock();resultiteration(N);finishclock();cout递推结果resultendl用时finish-startmsendl;return0;}运行结果截图任务4比较两种方法在解决相同规模问题时执行时间上的优劣统计算法的执行时间可利用折线图进行比较。2.3 递归求解问题的思考方式任务5汉诺塔问题编写程序输出汉诺塔问题全部移动步骤初始状态所有圆盘在 A 塔借助 B 塔移动到 C 塔。算法描述如下hanoi(intn,chara,charb,charc){//把n个盘子从a柱借助b柱移动到c柱if(n0){hanoi(n-1,a,c,b);//n-1个盘子从a借助c移动到bprintf(a,c);//1个盘子从a移动到chanoi(n-1,b,a,c);//n-1个盘子从b借助a移动到c}}源程序代码及运行结果截图#includeiostream#includectimeusingnamespacestd;voidhanoi(intn,chara,charb,charc)//汉诺塔,n个从小到大从上到下排列在a柱的圆盘a,b,c三根柱子{//把n个盘子从a柱移动到c柱if(n0){hanoi(n-1,a,c,b);couta-cendl;hanoi(n-1,b,a,c);}}intmain(){intN7,start,finish;startclock();hanoi(N,a,b,c);finishclock();cout用时finish-startmsendl;return0;}运行结果截图任务6观察汉诺塔问题的计算时间并推测复杂度输入不同的 n 值观察并记录汉诺塔问题的计算时间绘制折线图并推测汉诺塔问题在问题规模为 n 时的复杂度。汉诺塔问题的复杂度为O(2ⁿ)。2.4 利用递归和递推两种方式求解问题任务7输出不大于 9 位正整数的逆序输入任意一个不大于 9 位的 int 型正整数输出各位数的逆序形式例如输入 12345输出 54321。请分别利用递归和递推两种方式编写程序求解问题。源程序代码及运行结果截图#includeiostreamusingnamespacestd;voidrecursion(intn)//递归输出不大于9位的正整数的逆序{if(n0)return;coutn%10;nn/10;recursion(n);}voiditeration(intn)//递推输出不大于9位的正整数的逆序{while(n0){coutn%10;nn/10;}}intmain(){intN;cout请输入一个不大于9位的正整数;cinN;cout递归结果为;recursion(N);coutendl递推结果为;iteration(N);return0;}运行结果截图3. 实验总结1采用递归法求解问题的基本思路是将规模较大的问题分解为规模较小且与原问题结构相同的子问题通过不断调用自身来逐步缩小问题规模直到达到可直接求解的边界条件递归出口再逐层返回结果完成求解。递归的核心在于找到递归方程和终止条件把复杂问题转化为简单问题的重复求解。2递归与递推的对比分析递归代码简洁、逻辑清晰符合人的思维习惯但每次函数调用都会产生额外的栈空间开销和函数调用开销且存在大量重复计算如斐波那契数列效率较低n 较大时可能导致栈溢出。递推使用循环结构从已知的初始条件出发逐步推导出结果没有函数调用开销时间和空间效率更高但代码相对繁琐需要人为设计递推关系。3在解决实际问题时应优先考虑递推迭代方案当问题天然具有递归结构如汉诺塔、树的遍历且规模可控时递归是更直观的选择。