迭代算法、递归算法区别

《迭代算法、递归算法区别》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、迭代算法、递归算法区别迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立

2、是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件。例1：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新

3、生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月时，该饲养场共有兔子多少只?分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1，第2个月时兔子的只数为u2，第3个月时兔子的只数为u3，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有以下是引用片段：u1=1，u2=u1+u1×1=2，u3=u2+u2×1=4，……　　根据这个规律，可以归纳出下面的递推公式：以下是引用片段：　　un=un-1×2(n≥2)　　对应un和un-1，定义两个迭代变量y和x，

4、可将上面的递推公式转换成如下迭代关系：以下是引用片段：　　y=x*2　　x=y　　让计算机对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。参考程序如下：以下是引用片段：　　cls　　x=1　　fori=2to12　　y=x*2　　x=y　　nexti　　printy　　end　　例2：阿米巴用简单分裂的方式繁殖，它每分裂一次要用3分钟。将若干个阿米巴放在一个盛满营养参液的容器内，45分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴220个。试问，开始的时候往容器内放了多少个阿米巴?请

5、编程序算出。分析：根据题意，阿米巴每3分钟分裂一次，那么从开始的时候将阿米巴放入容器里面，到45分钟后充满容器，需要分裂45/3=15次。而“容器最多可以装阿米巴220个”，即阿米巴分裂15次以后得到的个数是220。题目要求我们计算分裂之前的阿米巴数，不妨使用倒推的方法，从第15次分裂之后的220个，倒推出第15次分裂之前(即第14次分裂之后)的个数，再进一步倒推出第13次分裂之后、第12次分裂之后、……第1次分裂之前的个数。设第1次分裂之前的个数为x0、第1次分裂之后的个数为x1、第2次分裂之后的

6、个数为x2、……第15次分裂之后的个数为x15，则有以下是引用片段：　　x14=x15/2、x13=x14/2、……xn-1=xn/2(n≥1)　　因为第15次分裂之后的个数x15是已知的，如果定义迭代变量为x，则可以将上面的倒推公式转换成如下的迭代公式：　　x=x/2(x的初值为第15次分裂之后的个数220)让这个迭代公式重复执行15次，就可以倒推出第1次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值，我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下：以下是引用片段：　　c

7、ls　　x=2^20　　fori=1to15　　x=x/2　　nexti　　printx　　end　　例3：验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数n，若n为偶数，则将其除以2;若n为奇数，则将其乘以3，然后再加1。如此经过有限次运算后，总可以得到自然数1。人们把谷角静夫的这一发现叫做“谷角猜想”。要求：编写一个程序，由键盘输入一个自然数n，把n经过有限次运算后，最终变成自然数1的全过程打印出来。分析：定义迭代变量为n，按照谷角猜想的内容，可以得到两种情况

8、下的迭代关系式：当n为偶数时，n=n/2;当n为奇数时，n=n*3+1。用QBASIC语言把它描述出来就是：以下是引用片段：　　ifn为偶数then　　n=n/2　　else　　n=n*3+1　　endif　　这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次，才能使迭代变量n最终变成自然数1，这是我们无法计算出来的。因此，还需进一步确定用来结束迭代过程的条件。仔细分析题目要求，不难看出，对任意给定的一个自然数n，只要经过有限次运算后，能够得到自然数1