第十四章迭代和递归

第十四章迭代和递归

一、迭代L迭代的特点迭代是一种根据反馈不断重复的过程，其最终目的是为了使结果更符合目标的需求在计算机中我们也经常使用到这种方法，让计算机重复执行一段指令或代码，这组指令或代码每执行一次，都会从原值中推导出一个新值2,迭代的三要素⑴迭代变量即从旧值中推导出的新值⑵迭代关系式即用旧值推导出新值的公式或方法⑶控制迭代过程即迭代必须有结束条件3,迭代案例及分析

3.1牛顿迭代法求a的平方根基本思路先估测一个近似值然后不断令等于和的平均数经过多次迭代之后，X,x xa/x x的值将逐渐逼近的平方根这种方法只能无限接近平方根，对完全平方数往往无法得出整数a根结果迭代三要素分析；迭代变量:近似值

[1]x；⑵迭代关系式x=x+a/x/2控制迭代过程前后两次产生的的差的绝对值小于

[3]x10-5a=3x=a/2while absx+a/x/2-x

0.00001:x=x+a/x/2的平方根为printa,:roundx+a/x/2,

43.2斐波那契数列求和提示:斐波那契数列1,1,2,3,5,8,13,2L...迭代三要素分析迭代变量

[1]an⑵迭代关系式:a=a-i+a-2n n n控制迭代过程

[3]n=15al=a2=1sum=0#求前位斐波那契数的和for iin range15:15sum=sum+alal,a2=a2,al+a2printsum

3.3欧几里得算法求最大公约数又称辗转相除法def gcdmn:Jwhile n!=0:m,n=n,m%nreturn mprintgcd24,15

二、递归L递归的特点有一类问题的解法具有这样的特征，在大问题的解决中嵌套着与原问题相似的规模较小的问题，这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己实现计算机在执行递归程序时，是通过栈的调用来实现的递归算法的执行过程可以拆分成两个阶段⑴递推:将原问题推导到问题边界，每层向下递推时都需要将当前层状态入栈；⑵回归:从边界将结果层层返回，每层向上回归时都需要从栈中取出上一层状态，当栈为空时，回归结束返回值6第4次调用图521递归调用过程

2.递归解决问题需要满足两个条件⑴递归公式将规模为的问题缩小为规模为的问题的方法⑵递归边界当缩小到一定nn-1n值时，可以直接给出结果的时候

3.递归案例及解析求阶乘结果

3.1n提示n!=l*2*3*4*5*...*n-l*n递归条件分析递归公式

[1]facn=n*facn-l⑵递归边界当时，即n=l facl=ldef facn:if n==1:return1else:return n*facn-lprintfac15汉诺塔问题

3.2汉诺塔游戏的装置是一块铜板，上面有三根柱，其中最左侧的一根柱上放着从大到小的个圆n盘游戏目标是把所有圆盘从最左侧柱上移动到最右侧柱上，中间的柱作为过渡游戏规定每次只能移动一个圆盘，且大圆盘不能压在小圆盘上面递归条件分析⑴递归公式层汉诺塔”问题可以分解为“n图5233个圆盘的汉诺塔模型；层”从到L“n-1a b；层从到

2.“1”a c；层从到

3.“n-1”b c⑵递归边界当时，直接从到n=l ac曲起始柱，中间柱，目标柱def hanoin,a,b,c:b cifn==l:print,,{}-{}n.format ac returnelse:hanoin-l,a,c,b hanoil,a,b,c hanoin-l,b,a,c returnhanoi3,AJB,C

三、迭代和递归的关系,迭代的迭代公式和递归的递归公式，本质上都是递推公式

1.当一个问题可以用迭代处理，则这个问题也一定可以用递归处理，反之也成立

2.对于同一个问题，用迭代处理的效率一定优于用递归处理，但递归的代码可读性往往更好3。