5.2.2递归　课件　2022—2023学年浙教版（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的阶乘的相应的程序及测试结果如下： def fac(n): if n==0: s=1 else: s=n*fac(n-1) return s print(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的变化 情况： def fac(n): if n==0: s=1 else: print(str(n)+‘*fac(‘+str(n-1)+’)’) s=n*fac(n-1) return s print(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 = 1 for i in range(3, n+1): __________ __________ __________ print(c) def fib(n): if n<1: ________ elif n==1: __________ else: _________________ n=int(input("请输入正整数:")) print(fib(n)) c=a+b a=b b=c return 0 return 1 return fib(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程序如下： def fg(n): if n==1: return 1