14.迭代和递归 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十四章 迭代和递归 一、迭代 1.迭代的特点 迭代是一种根据反馈不断重复的过程，其最终目的是为了使结果更符合目标的需求。在计算机中我们也经常使用到这种方法，让计算机重复执行一段指令或代码，这组指令或代码每执行一次，都会从原值中推导出一个新值。 2.迭代的三要素： (1)迭代变量：即从旧值中推导出的新值 (2)迭代关系式：即用旧值推导出新值的公式或方法 (3)控制迭代过程：即迭代必须有结束条件。 3.迭代案例及分析 3.1牛顿迭代法求a的平方根 基本思路：先估测一个近似值x，然后不断令x等于x和a/x的平均数。经过多次迭代之后，x的值将逐渐逼近a的平方根。这种方法只能无限接近平方根，对完全平方数往往无法得出整数根结果。 迭代三要素分析： [1]迭代变量：近似值x； [2]迭代关系式：x=(x+a/x)/2； [3]控制迭代过程：前后两次产生的x的差的绝对值小于10-5 a = 3 x= a/2 while abs((x+a/x)/2-x)>0.00001:     x = (x+a/x)/2 print(a,"的平方根为",round((x+a/x)/2,4)) 3.2斐波那契数列求和 提示：斐波那契数列：1,1,2,3,5,8,13,21.... 迭代三要素分析： [1]迭代变量：an [2]迭代关系式：an=an-1+an-2 [3]控制迭代过程：n=15 a1 = a2 = 1 sum = 0 for i in range(15):   #求前15位斐波那契数的和     sum = sum + a1     a1,a2 = a2,a1+a2 print(sum) 3.3欧几里得算法求最大公约数（又称辗转相除法） def gcd(m,n):     while n != 0:         m,n=n,m%n     return m print(gcd(24,15)) 二、递归 1.递归的特点 有一类问题的解法具有这样的特征，在大问题的解决中嵌套着与原问题相似的规模较小的问题，这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己实现。计算机在执行递归程序时，是通过栈的调用来实现的。递归算法的执行过程可以拆分成两个阶段： (1)递推:将原问题推导到问题边界，每层向下递推时都需要将当前层状态入栈； (2)回归:从边界将结果层层返回，每层向上回归时都需要从栈中取出上一层状态，当栈为空时，回归结束。 2.递归解决问题需要满足两个条件 (1)递归公式：将规模为n的问题缩小为规模为n-1的问题的方法 (2)递归边界：当n缩小到一定值时，可以直接给出结果的时候 3.递归案例及解析 3.1 求n阶乘结果 提示：n!=1*2*3*4*5*...*(n-1)*n 递归条件分析 [1]递归公式：fac(n)=n*fac(n-1) [2]递归边界：当n=1时，即fac(1)=1 def fac(n):     if n == 1:         return 1     else:         return n*fac(n-1) print(fac(15)) 3.2汉诺塔问题 汉诺塔游戏的装置是一块铜板，上面有三根柱，其中最左侧的一根柱上放着从大到小的n个圆盘。游戏目标是把所有圆盘从最左侧柱上移动到最右侧柱上，中间的柱作为过渡。游戏规定每次只能移动一个圆盘，且大圆盘不能压在小圆盘上面。 递归条件分析： [1]递归公式：“n层汉诺塔”问题可以分解为： 1.“n-1层”从a到b； 2.“1”层从a到c； 3.“n-1”层从b到c； [2]递归边界：当n=1时，直接从a到c def hanoi(n,a,b,c):   #a起始柱,b中间柱,c目标柱     if n==1:         print("{}->{}".format(a,c))         return     else:         hanoi(n-1,a,c,b)         hanoi(1,a,b,c)         hanoi(n-1,b,a,c)         return hanoi(3,'A','B','C') 三、迭代和递归的关系 1.迭代的迭代公式和递归的递归公式，本质上都是递推公式。 2.当一个问题可以用迭代处理，则这个问题也一定可以用递归处理，反之也成立。 3.对于同一个问题，用迭代处理的效率一定优于用递归处理，但递归的代码可读性往往更好。 学科网（北京）股份有限公司 $