递归递归与迭代.doc

递归与迭代

递归与迭代递归与迭代

递归与迭代

迭代(iterative)和递归(recursive)可以相互转化。常常要求把递归转化为迭代。因为递归得耗费大量时间。最大公因数最大公因数又称最大公约数英文Greatest Common Divider缩写GCD(n(≥2)个自然数a1,a2,… ,an的最大公因数通常有两种定义方式: 1.它们的所有公因数中最大的那一个;

2.如果自然数m是这n个自然数的公因数且这n个数的任意公因数都是m的因数就称m是这n个数的最大公因数(a1,a2,… ,an的最大公因数在国内常记为(a1,a2,… ,an)  国际通用记号为g.c.d. (a1,a2,… ,an) (

例:求最大公因数程序: (以下程序是伪码描述)递归法:procedure GCD(a,b)//假设a>b>=0// if b==0 then return(a) else return(GCD(b,a modb) )//mod运算为模运算在此式中意为求a与b的模// endifend GCD

转化为迭代:procedure GCD2(a,b) while b!=0 do t=b; b=(a mod b) ; a=t;repeat return(a)end GCD2

迭代的另外一个example:for( ; ; ) { a[2] = a[0] + a[1] ; a[0] = a[1] ; a[1]= a[2] ; }就是反复套用一个公式

一个讨论:

看过这样一道题 问 “程序结构化设计的三种基础结构顺序、选择、循环是不是必须的,”当然你知道这样一个论断只要有这三种就足够

了;但是能不能更少呢,答案是“可以” 原因就是递归能取代循环的作用例如下面的对一个数组里面元素求和的函数:float rsum (float a[] , const int n) {if (n <= 0) return 0;elsereturn rsum(a, n – 1) +a[n – 1] ; }

实际上就是:sum = 0;for (int i = 0; i < n; i++) sum += a[i] ;

但实际的情况是任何的一种语言里面都有循环结构但不是任何的语言都支持递归;套用一句话递归是万能的但没有递归不是万万不能的。然而我看到现在的某些人不管什么问题都要递归 明明循环是第一个想到的方法偏偏费尽脑筋去寻找递归算法。

经常的看到“递归算法” 、 “非递归算法” 这种提法没有语义上的问题并且我自己也这样用——递归的算法。但这也正说明了递归不是算法他是一种思想正是因为某个算法的指导思想是递归的所以才被称为递归算法;而一个有递归算法的问题 当你不使用递归作为指导思想这样得到的算法就是非递归算法。 ——而对于循环能处理的问题都有递归解法在这个意义上说循环算法都可以称为非递归算法。

我在这咬文嚼字没什么别的意思只是想让大家知道能写出什么样的算法关键是看你编写算法时的指导思想。如果一开始就想到了循环、迭代的方法你再费心耗神去找什么递归算法——即使找到了一种看似“简洁”

的算法 由于他的低效实际上还是废物——你还在做这种无用功干什么,典型的学究陋习。如果你仅仅想到了递归的方法现在你想用栈来消解掉递归你做的工作仅仅是把系统做的事自己做了你又能把效率提高多少,盲目的迷

信消解递归就一定能提高效率是无根据的——你做的工作的方法如果不得当的话甚至还不如系统原来的做法。

从学排列组合那天开始我所知道的阶乘就是这个样子n! =

1×2×……n。如果让我来写阶乘的算法我也只会想到从1乘到n。再如斐波那契数列如果有人用自然语言描述的话一定是这样的开始两项是0、 1 以后的每项都是前面两项的和。所以让我写也只会得到“保存前两项然后相加得到结果”的迭代解法。 ——现在只要是讲到递归几乎就有他们的登场美其名曰:“定义是递归的所以我们写递归算法” 。我想问的是定义的递归抽象是从哪里来的,显然阶乘的定义是从一个循环过程抽象来的斐波那契数列的定义是个迭代的抽象。于是我们先从一个本不是递归的事实抽象出一个递归的定义然后我们说 “因为问题的定义是递归的 因此我们很容易写出递归算法” 接着说 “我们也能将这个递归算法转化为循环、迭代算法” 给人的感觉就像是

1÷3,0.33…… 

0.33……×3,0.99…… 然后我们花了好大的心智才明白1,0.99…… 。

还是有那么些人乐此不疲是凡讲到递归就要提到这两个结果没有一个学生看到阶乘那样定义没有疑问的没有一个对于那个递归的阶乘函数抱有钦佩之情的——瞎折腾什么呢,所以如果要讲递归就要一个令人信服的例

塔莫属。 子而这个例子非汉诺

出几道有关迭代递归的题以供学习参考

1:迭代方法求方程题:函数countValue()实现下列功能:利用以下所示的简单迭代方法求方程:cos(x)-x=0的一个实根。 Xn+1=cos(Xn)迭代步骤如下: (1)取X1初值为0.0; (2)X0=X1把X1的值赋给X0; (3)X1=cos(X0) 求出一个新的X1 ; (4)若

X0-X1的绝对值小于0.000001执行步骤(5) 否则执行步骤(2) ; (5)所求X1就是方程cos(X)-X=0的一个实根作为函数值返回float countValue(void)

{ x1=0.0; do { x0=x1 ; x1=cos(x0) ; } while(fab(x0-x1)>=0.000001)return x1 ; }

欢迎您阅读该资料希望该资料能给您的学习和生活带来帮助如果您还了解更多的相关知识也欢迎您分享出来让我们大家能共同进步、共同成长。

欢迎使用“递归与迭代”使用该文档doc格式如大家有其它疑问或者新的见解欢迎大家互相交流、互相进步。