资源描述：
《递推.递归.迭代说明》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、递推基本介绍 递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法. 递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。递推算法 递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法. 【例1】 植树节那天，有五位同学参加了植树活动，他们完成植树的棵树都不相同。问第一位同学植了多少棵时，他指着旁边的第二位
2、同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；...如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？ 分析：设第一位同学植树的棵树为a1,欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算： (1)a5=10; (2)a4=a5+2=12; (3)a3=a4+2=14; (4)a2=a3+2=16; (5)a1=a2+2=18; Pascal程序： ProgramExaml; Vari
3、,a:byte; begin a:=10; fori:=1to4do a:=a+2; writeln('TheNumis',a); readln; end. 本程序的递推运算可用下图示表示： 初始值a:=10-----i=1,a=a+2(12)-----i=2,a=a+2(14)------i=3,a=a+2(16)-----i=4,a=a+2(18)----输出a值 例2： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？ 当n个编号元素放在n个编号位置,元素编号与
4、位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推. 第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法; 第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法; 综上得到 M(n)=(n-1)[M(n-2)+M(n-1)]递推算法以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运
5、算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）先一步的结果。迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推
6、出它的一个新值。目录算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点算法1.确定迭代变量2.建立迭代关系式3.对迭代过程进行控制4.举例递归的基本概念和特点展开编辑本段算法 利用迭代算法解决问题，需要做好以下三个方面的工作：确定迭代变量 在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。建立迭代关系式 所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用
7、递推或倒推的方法来完成。对迭代过程进行控制 在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。举例 例1：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到
8、第12个月时，该饲养场共有兔子多少只？ 分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1，第2个月时兔子的只数为u2，第3个月时兔子的只数为u3，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有 u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，…… 根据这个规律，可以归
