迭代与递归的区别

《迭代与递归的区别》由会员分享，可在线阅读，更多相关《迭代与递归的区别（18页珍藏版）》请在金锄头文库上搜索。

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

2、是编写迭代程序必须考 虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需 的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对 迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月 开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去， 问到第 12 个月时，该饲养场共有兔子多少只？分析： 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ，第 2 个月时兔

3、子的只数为 u2 ，第 3 个月时兔子的只数为 u3 ，根 据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 = 1 , u 2 = u 1 + ulXl = 2 , u 3 = u 2 + u2Xl = 4 ,根据这个规律，可以归纳出下面的递推公式：u n = u n 1 X 2 （n 三 2）对应 u n 和 u n 1 ，定义两个迭代变量 y 和 x ，可将上面的递推公式转 换成如下迭代关系：y=x*2 x=y让计算机对这个迭代关系重复执行 11 次，就可以算出第 12 个月时的兔子数 参考程序如下： clsx=1 for i=2 to 12y=x*2 x=ynex

4、t iprint yend例 2： 阿米巴用简单分裂的方式繁殖，它每分裂一次要用 3 分钟。将若干个 阿米巴放在一个盛满营养参液的容器内， 45 分钟后容器内充满了阿米巴。已知 容器最多可以装阿米巴 2 20 个。试问，开始的时候往容器内放了多少个阿米 巴？请编程序算出。分析：根据题意，阿米巴每 3分钟分裂一次，那么从开始的时候将阿米巴放入 容器里面，到 45 分钟后充满容器，需要分裂 45/3=15 次。而“容器最多可以 装阿米巴 220 个”，即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求 我们计算分裂之前的阿米巴数，不妨使用倒推的方法，从第 15次分裂之后的 2 20个，倒

5、推出第 15次分裂之前（即第 14次分裂之后）的个数，再进一步倒 推出第 13 次分裂之后、第 12 次分裂之后、第 1 次分裂之前的个数。设第 1次分裂之前的个数为 x 0 、第 1次分裂之后的个数为 x 1、第 2 次 分裂之后的个数为 x 2、第 15次分裂之后的个数为 x 15 ，则有x 14 =x 15 /2 、 x 13 =x 14 /2 、x n-1 =x n /2 （n 三 1）因为第 15 次分裂之后的个数 x 15 是已知的，如果定义迭代变量为 x ，则可 以将上面的倒推公式转换成如下的迭代公式：x=x/2 （ x的初值为第15次分裂之后的个数2 20 ）让这个迭代公式重复

6、执行 15 次，就可以倒推出第 1次分裂之前的阿米巴个数。 因为所需的迭代次数是个确定的值，我们可以使用一个固定次数的循环来实现对 迭代过程的控制。参考程序如下：cls x=2 20for i=1 to 15 x=x/2next iprint xend例 3 ： 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现 象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2 ；若 n 为奇数，则 将其乘以 3 ，然后再加 1 。如此经过有限次运算后，总可以得到自然数 1 。 人们把谷角静夫的这一发现叫做“谷角猜想”。要求：编写一个程序，由键盘输入一个自然数 n ，把 n 经过有限次

7、运算后，最 终变成自然数 1 的全过程打印出来。分析： 定义迭代变量为 n ，按照谷角猜想的内容，可以得到两种情况下的迭代 关系式：当 n 为偶数时， n=n/2 ；当 n 为奇数时， n=n*3+1 。用 QBASIC 语 言把它描述出来就是：if n 为偶数 thenn=n/2elsen=n*3+1end if这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次，才 能使迭代变量 n 最终变成自然数 1 ，这是我们无法计算出来的。因此，还需进 一步确定用来结束迭代过程的条件。仔细分析题目要求，不难看出，对任意给定 的一个自然数 n ，只要经过有限次运算后，能够得到自然数 1

8、，就已经完成了 验证工作。因此，用来结束迭代过程的条件可以定义为： n=1 。参考程序如下：clsinput Please input n=;n do until n=1if n mod 2=0 then rem 如果 n 为偶数，则调用迭代公式 n=n/2 n=n/2 . print ;n;elsen=n*3+1 . print ;n;end ifloopend迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=O，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：(1) 选一个方程的近似根，赋给变量 x0；(2) 将x0的值保存于变量xl,然后计算

9、g(xl),并将结果存于变量xO；(3) 当xO与xl的差的绝对值还小于指定的精度要求时，重复步骤(2)的计 算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的 xO 就认为是方程的根。上述算法用 C 程序的形式表示为：【算法】迭代法求方程的根 x0=初始近似根；do xl=xO；xO=g(xl)；/*按特定的方程计算新的近似根*/ while ( fabs(xO-xl)Epsilon) ；printf (“方程的近似根是%fn”，xO)；迭代算法也常用于求方程组的根，令X=( xO， xl， xn-l)设方程组为：xi=gi(X) (I=O， l， n-l)则求方程组

10、根的迭代算法可描述如下：【算法】迭代法求方程组的根 for (i=0;iX二初始近似根；do for (i=0；iy=X；for (i=0；iX=gi(X)；for (delta=0.0,i=0；iif (fabs(y-X)delta) delta=fabs(y-X)； while (deltaEpsilon) ；for (i=0；iprintf (“变量 x%d的近似根是 f”，I, x)； printf(“n”)；具体使用迭代法求根时应注意以下两种可能发生的情况：(1) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循 环，因此在使用迭代算法前应先考察方程是否有解，并在程序

11、中对迭代的次数给 予限制；(2) 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理， 也会导致迭代失败。递归递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采 用，为此在进一步介绍其他算法设计方法之前先讨论它。能采用递归描述的算法通常有这样的特征：为求解规模为 N 的问题，设法将它分 解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这 些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并 从这些更小问题的解构造出规模较大问题的解。特别地，当规模 N=1 时，能直接 得解。【问题】编写计算斐波那契(Fibonacci )数列

12、的第n项函数fib (n)。 斐波那契数列为：0、1、1、2、3、，即：fib(0)=0；fib(1)=1；fib(n)=fib(n-1)+fib(n-2) (当 n1 时)。写成递归函数有：int fib(int n) if (n=0) return 0；if (n=1) return 1；if (n1) return fib(n-1)+fib(n-2)； 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题(规 模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例 中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(

13、n)， 必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2)，又必须先计 算fib(n-3)和fib(n-4)。依次类推，直至计算fib( 1)和fib(O),分别能立即得 到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当 n为1和0的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解， 例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，在得到了 fib(n-1) 和fib(n-2)的结果后，返回得到fib(n)的结果。在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当 递推

14、进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一 系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的 执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推 算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推 算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算 出要求的第n项。【问题】 组合问题问题描述：找出从自然数1、2、n中任取r个数的所有组合。例如n=5，r=3 的所有组合为： (1)5、 4、 3 (2)5、 4、 2 (3)5、 4、 1

15、(4) 5、3、 2(5)5、3、1(6)5、2、1(7)4、3、 2(8)4、3、1(9)4、2、1(10)3、 2、 1 分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设 函数为void comb(int m,int k)为找出从自然数1、2、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的 m-1 个数中取 k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取 k-1个数的组合问题。设函数引入工作数组a存放求出的组合的数字，约定函 数将确定的k个数字组合的第一个数字放在ak中，当一个组合求出后，才将 a中的一个组合输出。第一个数可以是m、m-1、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续 递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中 的函数 comb。【程序】# include# define MAXN 100int aMAXN;void comb(int m,int k) int i,j;