5.2.2 递归 ppt课件-2023新浙教版（2019）《高中信息技术》选修1.pptx

1、5.2.2 递归大问题的解决中嵌套着与原问题相似的规模较小的问题。这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。在数据结构与算法设计中，递归十分有用，它往往能使函数的定义和算法的描述简洁且易于理解，极大地减少程序代码量。如前面学过的的二叉树，由于其本身固有的递归特性，特别适合用递归的形式来描述。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界，如问题规模缩减为0或1

2、时，能直接得解。因此，在设计递归算法时，要满足两个条件：确定递归公式和递归结束条件。例：利用递归算法求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)(n0)按照这个公式，可以将求n!的问题转化成求(n-1)!的问题；而求(n-1)!的问题，又可以转化成求(n-2)!的问题；求（n-2）!的问题，又可以转化成求(n-3)！的问题，如此继续，直到最后转化成求0！的问题。再反过来，依次求出1！，2！，直到最后求出n

3、!。因此，在该问题中，递归公式是fac(n)=n*fac(n-1),当n=0时递归结束。求n的阶乘的相应的程序及测试结果如下：def fac(n):if n=0:s=1 else:s=n*fac(n-1)return sprint(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对于阶乘问题，

4、可以在原程序上通过添加一条语句来跟踪参数n的变化情况：def fac(n):if n=0:s=1 else:print(str(n)+*fac(+str(n-1)+)s=n*fac(n-1)return sprint(fac(3)3*fac(2)2*fac(1)1*fac(0)6利用迭代和递归思想解决问题时有何区别？算法实现时两者有哪些优缺点？迭代的思想，是一种由旧值不断推出新值的过程。它包括三个方面：一、确定迭代变量；二、建立迭代关系式；三、控制迭代过程，使程序能够停止下来。递归思想，是一种把数据规模较大、较复杂的问题分解成规模较小的问题，进而构造出整个问题解的思想方法。递归算法的执行过程分

5、递推和回归两个阶段，其中的关键是如何建立递归关系式与控制程序停止。一般而言，迭代思想实现的难点在于建立正确的迭代公式，通常要借助循环语句。而递归思想比较难以理解，程序编写简洁，但递归程序的效率相对不高。练习：1.验证角谷猜想。所谓角谷猜想，是指对于任意一个正整数，若是奇数，则乘3加1；若是偶数，则除以2。得到的结果再按照上述规则重复处理，最终总能够得到1。要求：编写一个程序，输入一个正整数n，把n经过有限次运算后，输出最终变成1的全过程。a=int(input(“请输入一个正整数：”)while a!=1:print(a)if a%2=1:a=a*3+1 else:a=a/2print(a)请

6、输入一个正整数：212164321684212.斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34，其定义如下：f(0)=0f(1)=1f(n)=f(n-1)+f(n-2)(n=2)编程求f(40)的值，请分别用迭代和递归算法实现，并分析这两种算法的时间复杂度。迭代程序迭代程序递归程序递归程序f0=0f1=1n=2while n=40:f=f1+f0 f0=f1 f1=f n=n+1print(f1)def fib(n):if n=2开始计算，用f0和f1两个数相加求出结果，重复执行n-1次即可，算法的时间复杂度与n成正比，即算法的时间复杂度为O(n)。利用递归算法求斐波那契

7、数列，要求解fib(n)，必须先计算fib(n-1)和fib(n-2)，计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)以此类推，直至计算到fib(1)和fib(0)，然后回归得到fib(n-1)和fib(n-2)的结果，最后得到fib(n)。递归调用的过程可以用二叉树的形式表示，如fib(5)的调用过程如下图所示。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)递归调用的二叉树表示递归调用次数即为二叉树的节点个数

8、（深度为n的二叉树最多有2n-1个节点），即时间复杂度为O(2n)。4.楼梯上有8级台阶，从下开始往上走，每次可以走一步或者两步，自定义函数fg可以计算走完n级台阶有多少种走法。实现对应功能的Python程序如下：def fg(n):if n=1:return 1 elif n=2:return 2 else:return fg(n-1)+fg(n-2)Print(走完8级台阶的方法共有，fg(8)，种)则走完这8级台阶的走法有（）A.34种 B.35种 C.36种 D.37种A4.递归过程的实现过程分为两个阶段，分别是（）A.枚举和回归B.递推和回归C.递推和递归D.试探和回归B6.递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是（）A.数组B.队列C.栈D.链表C谢 谢