递归　课件　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

5.2.2递归大问题的解决中嵌套着与原问题相似的规模较小的问题。这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。递归的作用：

能使函数的定义和算法的描述简洁且易于理解，极大地减少程序代码量。能采用递归描述的算法通常有这样的特征：

为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，递归核心整体方法和局部方法是一致的。在设计递归算法时，要满足两个条件：确定递归公式和递归结束条件。例：利用递归算法求n的阶乘（n!=1*2*…*n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n!=n*(n-1)!，并且规定0!=1。设函数fac(n)=n!，则fac(n)可表示为：fac(n)=1(n=0)n*fac(n-1)(n>0)按照这个公式，可以将求n!的问题转化成求(n-1)!的问题；而求(n-1)!的问题，又可以转化成求(n-2)!的问题；求（n-2）!的问题，又可以转化成求(n-3)的问题，如此继续，直到最后转化成求0！的问题。再反过来，依次求出1！，2！，…，直到最后求出n!。因此，在该问题中，递归公式是fac(n)=n*fac(n-1),当n=0时递归结束。求n的阶乘的相应的程序及测试结果如下：deffac(n):ifn==0:s=1else:s=n*fac(n-1)returnsprint(fac(3))当主程序执行函数fac(3)时，引起第1次函数调用，进入函数后，参数n=3，应执行计算3*fac(2)。直到计算fac(0)，将引起对函数fac的第4次调用。以上调用的执行和返回情况，如下图所示。fac(3)3*fac(2)第1次调用第2次调用2*fac(1)第3次调用1*fac(0)第4次调用1递归调用过程返回值1返回值1返回值2返回值6递推回归对于阶乘问题，可以在原程序上通过添加一条语句来跟踪参数n的变化情况：deffac(n):ifn==0:s=1else:print(str(n)+‘*fac(‘+str(n-1)+’)’)s=n*fac(n-1)returnsprint(fac(3))3*fac(2)2*fac(1)1*fac(0)6例.斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34，…，其定义如下：f(n)=f(n-1)+f(n-2)(n>=2)编程求f(n)的值，请分别用迭代和递归算法实现，并分析这两种算法的时间复杂度。迭代程序递归程序n=int(input("请输入正整数:"))a=b=1foriinrange(3,n+1):______________________________print(c)

deffib(n):ifn<1:

________elifn==1:

__________else:

_________________n=int(input("请输入正整数:"))print(fib(n))c=a+ba=bb=creturn0return1returnfib(n-1)+fib(n-2)时间复杂度为O(n)fib(5)fib(3)fib(4)fib(3)fib(2)fib(2)fib(1)fib(1)fib(1)fib(1)fib(0)fib(2)fib(1)fib(0)fib(1)fib(5)递归调用的二叉树表示递归调用次数即为二叉树的节点个数（深度为n的二叉树最多有_____个节点），即时间复杂度为______。O(2n)2n-1例.楼梯上有8级台阶，从下开始往上走，每次可以走一步或者两步，自定义函数fg可以计算走完n级台阶有多少种走法。实现对应功能的Python程序如下：deffg(n):ifn==1:return1elifn==2:return2else:returnfg(n-1)+fg(n-2)Print(‘走完8级台阶的方法共有’，fg(8)，‘种’)则走完这8级台阶的走法有（）A.34种B.35种C.36种D.37种A利用迭代和递归思想解决问题时有何区别？算法实现时两者有哪些优缺点？迭代的思想，是一种由旧值不断推出新值的过程。它包括三个方面：一、确定迭代变量；二、建立迭代关系式；三、控制迭代过程，使程序能够停止下来。递归思想，是一种把数据规模较大、较复杂的问题分解成规模较小的问题，进而构造出整个问题解的思想方法。递归算法的执行过程分__________两个阶段，其中的关键是如何建立递归关系式与控制程序停止。一般而言，迭代思想实现的难点在于建立正确的__________，通常要借助循环语句。而递归思想比较难以理解，程序编写简洁，但递归程序的效率_______________。递推和回归迭代公式相对不高例.递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是（）A.数组B.队列C.栈D.链表C汉诺塔游戏1.抽象与建模选择IDLE中的Help菜单——TurtleDemo——Minimal_Hanoi为了将n个盘子从A柱经过B柱移动到C柱，可建立如下模型：将n-1个盘子从A柱经过C柱移动到B柱将A柱中剩下的一个盘子移动到C柱将n-1个盘子从B柱经过A柱移动到C柱汉诺塔游戏2.设计算法（1）定义一个实现盘子移动的函数move。如将n个盘子从A柱经过B柱移动到C柱，可调用函数move(n,a,b,c)，其中，n表示A柱上的盘子个数，a、b、