信息与计算科学论文范文免费预览.doc

各专业毕业论文范文尽在道客巴巴下载学号：2006011269哈尔滨师范大学学士学位论文题 目 算法设计中的递归与非递归转换学 生 孙庆雨指导教师 栾丛海 讲师年 级 2006级专 业 信息与计算科学系 别 信息科学系学 院 数学科学学院哈 尔 滨 师 范 大 学学士学位论文开题报告论文题目 算法设计中的递归与非递归转换学生姓名 孙庆雨指导教师 栾丛海 讲师年 级 2006级专 业 信息与计算科学2009年 11月课题来源：自选题目课题研究的目的和意义：1.并不是每一门语言都支持递归的. 2.有助于理解递归的本质. 3.有助于理解栈、树等数据结构.国内外同类课题研究现状及发展趋势：近年来,计算机科学技术与计算机应用以惊人的速度发展。它已渗透到了人类生活的每一角 落.现代社会的各个领域无一例外地广泛使用着电子计算机.计算机知识已成为当代人类文化不可缺少的重要组成部分.研究与使用算法设计已成为必然. 在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解.课题研究的主要内容和方法，研究过程中的主要问题和解决办法：主要内容：算法设计中的递归和非递归转换主要方法：用栈来解决算法设计中的递归和非递归转换主要问题：实现算法设计中的递归和非递归转换解决方法：利用循环，递归调用树，栈实现算法设计中的递归和非递归转换课题研究起止时间和进度安排：2009年12月2日2010年2月9日 课题资料搜集整理2010年2月9日2010年4月6日 材料分析、撰写论文2010年4月20日 完成论文撰写、成稿课题研究所需主要设备、仪器及药品：计算机外出调研主要单位，访问学者姓名：指导教师审查意见：指导教师 （签字） 年 月 教研室（研究室）评审意见：_教研室（研究室）主任 （签字） 年 月系（部）主任审查意见：_系（部）主任 （签字） 年 月学 士 学 位 论 文题 目 算法设计中的递归与非递归转换学 生 孙庆雨指导教师 栾丛海 讲师年 级 2006级专 业 信息与计算科学系 别 信息科学系学 院 数学科学学院哈尔滨师范大学2010年5月算法设计中的递归和非递归转换孙庆雨摘要：算法设计中的递归和非递归转换是学习算法设计的基础，熟练地运用递归与非递归转换是算法设计的基础，在这篇论文中我就介绍几种算法设计中的递归与非递归的转换方法.让大家可以更好的实现算法设计中的递归和非递归转换。关键词：算法设计 递归与非递归 转换三种遍历树的算法 递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。一、为什么要学习递归与非递归的转换的实现方法 1.并不是每一门语言都支持递归的. 2.有助于理解递归的本质. 3.有助于理解栈,树等数据结构.二、三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个原理并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。 1)前序遍历 a)递归方式: void preorder_recursive(bitree t) /* 先序遍历二叉树的递归算法 */ if (t) visit(t); /* 访问当前结点 */ preorder_recursive(t-lchild); /* 访问左子树 */ preorder_recursive(t-rchild); /* 访问右子树 */ b)非递归方式 void preorder_nonrecursive(bitree t) /* 先序遍历二叉树的非递归算法 */ initstack(s); push(s,t); /* 根指针进栈 */ while(!stackempty(s) while(gettop(s,p)&p) /* 向左走到尽头 */ visit(p); /* 每向前走一步都访问当前结点 */ push(s,p-lchild); pop(s,p); if(!stackempty(s) /* 向右走一步 */ pop(s,p); push(s,p-rchild); 2)中序遍历 a)递归方式 void inorder_recursive(bitree t) /* 中序遍历二叉树的递归算法 */ if (t) inorder_recursive(t-lchild); /* 访问左子树 */ visit(t); /* 访问当前结点 */ inorder_recursive(t-rchild); /* 访问右子树 */ b)非递归方式 void inorder_nonrecursive(bitree t) initstack(s); /* 初始化栈 */ push(s, t); /* 根指针入栈 */ while (!stackempty(s) while (gettop(s, p) & p) /* 向左走到尽头 */ push(s, p-lchild); pop(s, p); /* 空指针退栈 */ if (!stackempty(s) pop(s, p); visit(p); /* 访问当前结点 */ push(s, p-rchild); /* 向右走一步 */ 3)后序遍历 a)递归方式 void postorder_recursive(bitree t) /* 中序遍历二叉树的递归算法 */ if (t) postorder_recursive(t-lchild); /* 访问左子树 */ postorder_recursive(t-rchild); /* 访问右子树 */ visit(t); /* 访问当前结点 */ b)非递归方式 typedef struct btnode* ptr; enum 0,1,2 mark; pmtype; /* 有mark域的结点指针类型 */ void postorder_nonrecursive(bitree t) /* 后续遍历二叉树的非递归算法 */ pmtype a; initstack(s); /* s的元素为pmtype类型 */ push (s,t,0); /* 根结点入栈 */ while(!stackempty(s) pop(s,a); switch(a.mark) case 0: push(s,a.ptr,1); /* 修改mark域 */ if(a.ptr-lchild) push(s,a.ptr-lchild,0); /* 访问左子树 */ break; case 1: push(s,a.ptr,2); /* 修改mark域 */ if(a.ptr-rchild) push(s,a.ptr-rchild,0); /* 访问右子树 */ break; case 2: visit(a.ptr); /* 访问结点 */ 三、实现递归与非递归的换转原理和例子原理分析： 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是数据,都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(bitree t) /* 先序遍历二叉树的递归算法 */ if (t) visit(t); /* 访问当前结点 */ preorder_recursive(t-lchild); /* 访问左子树 */ preorder_recursive(t-rchild); /* 访问右子树 */ visit(t)这个操作就是对当前数据进行的处理, preorder_recursive(t-lchild)就是把当前 数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的左子树和右子树c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的叶子结点.三个例子 好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得). 1.例子一: f(n) = n + ; (n = 2);这个例子相对简单一些,递归程序如下: int f_recursive(int n) int u1, u2, f; if (n 2) f = n + 1; else u1 = f_recursive(int)(n/2); u2 = f_recursive(int)(n/4); f = u1 * u2; return f; 下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点,我们看到当n = 0) switch(flagcp) case 0: /* 访问的是根结点 */ if (stackcp = 2) /* 左子树入栈 */ flagcp = 1; /* 修改标志域 */ cp+; stackcp = (int)(stackcp - 1 / 2); flagcp = 0; else /* 否则为叶子结点 */ stackcp += 1; flagcp = 2; break; case 1: /* 访问的是左子树 */ if (stackcp = 2) /* 右子树入栈 */ flagcp = 2; /* 修改标志域 */ cp += 2; stackcp = (int)(stackcp - 2 / 4); flagcp = 1; else /* 否则为叶子结点 */ stackcp += 1; flagcp = 2; break; case 2: /* */ if (flagcp - 1 = 2) /* 当前是右子树吗? */ /* * 如果是右子树, 那么对某一棵子树的后序遍历已经 * 结束,接下来就是对这棵子树的根结点的访问 */ stackcp - 2 = stackcp * stackcp - 1; flagcp - 2 = 2; cp = cp - 2; else /* 否则退回到后序遍历的上一个结点 */ cp-; break; return stack0; 算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向. 2.例子二 快速排序算法 递归算法如下: 代码: void swap(int array, int low, int high) int temp; temp = arraylow; arraylow = arrayhigh; arrayhigh = temp; int partition(int array, int low, int high) int p; p = arraylow; while (low high) while (low = p) high-; swap(array,low,high); while (low high & arraylow = p) low+; swap(array,low,high); return low; void qsort_recursive(int array, int low, int high) int p; if(low high) p = partition(array, low, high); qsort_recursive(array, low, p - 1); qsort_recursive(array, p + 1, high); 需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分,左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实partition函数就是对当前结点的访问). 再次进行递归调用树和栈的分析: 递归调用树:a)对当前结点的访问是调用partition函数;b)左子树:qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p +1, high); d)叶子结点:当low high时;e)可以看出这是一个先序调用的二叉树.栈:要保存的数据是两个表示范围的坐标. 代码: void qsort_nonrecursive(int array, int low, int high) int m50, n50, cp, p; /* 初始化栈和栈顶指针 */ cp = 0; m0 = low; n0 = high; while (mcp ncp) while (mcp 0) /* 压栈, 直到m1cp = 0 */ while (n1cp 0) /* 压栈, 直到n1cp = 0 */ cp+; m1cp = m1cp - 1; n1cp = n1cp - 1 - 1; /* 计算akm(m - 1, 1),当n = 0时 */ m1cp = m1cp - 1; n1cp = 1; /* 改栈顶为akm(m - 1, n + 1),当m = 0时 */ cp-; m1cp = m1cp - 1; n1cp = n1cp + 1 + 1; while (cp 0 | m1cp 0); return n10 + 1; 四、递归程序的分类及用途 递归程序分为两类:尾部递归和非尾部递归.上面提到的几个例子都是非尾部递归,在一个选择分支中有至少一个的递归调用.相对而言,尾部递归就容易很多了,因为与非尾部递归相比,每个选择分支只有一个递归调用, 我们在解决的时候就不需要使用到栈,只要循环和设置好循环体就可以了.下面再举几个尾部递归的例子吧,比较简单我就不多说什么了.1.例子一g(m, n) = 0 (m = 0, n = 0) = g(m - 1, 2n) + n; (m 0, n = 0)a)递归程序int g_recursive(int m, int n)if (m = 0 & n = 0) return 0;return (g_recurse(m - 1, 2*n) + n);b)非递归程序int g_nonrecursive(int m, int n)int p;for (p = 0; m 0 & n = 0; m-, n *= 2) p += n;return p;2.例子二f(n) = n + 1 (n = 0) = n * f(n/2) (n 0)a)递归程序int f_recursive(int n)if (n = 0) return 1;return (n * f_recurse(n/2);b)非递归程序int f_nonrecursive(int n)int m;for (m = 1; n 0; n /= 2) m *= n;return m+; 分析完了递归程序的分类,让我们回头看看在向非递归转换的过程中用到了什么来实现转换:1.循环,因为程序要在某个条件下一直执行下去,要代替递归程序,循环必不可少,对于尾部递归,循环结束的条件十分容易确定,只要按照不同分支的条件写出来就可以了.而对于非尾部递归程序,循环结束的条件一般是当栈为空时或者是结束了对递归调用树的遍历从树的根结点退出时,而且有的时候写成while()的形式,有时写成do .while的形式(如上面的akm函数),具体怎样,很难说清楚,取决于你对整个递归程序的分析。 2.递归调用树,树的结构在转换的过程中是不可见的,你不必为转换专门写一个树结构,不过能不能把递归调用中的树遍历方式以及叶子结点,左子树,右子树等元素确定好是你能否正确解决问题的关键(这一点已经在上面的分析过程中展露无疑),确定好这些后,剩下的工作大部分就是按照给出的几种不同的遍历树的方式把程序进行改写,这个过程就考验你对树结构还有遍历方式是否很好的掌握了(看出基础的重要了吗?如果回答是,那么和我一样好好的打好基础吧,一切都还不晚!).对于尾部递归而言,可以看作没有递归调用树,所以尾部递归的难度大大降低了。 3.栈,非尾部调用中需要栈来保存数据,这一点已经很清楚了,需要注意几个问题:a)栈有时可能会出现不够的情况,拿上面的akm函数来说,我用的50个元素的数组,你如果把m和n值设置得大一些,这个栈就不能用了,有时你的算法正确了,不过没有注意到这个问题还是会出错的;反过来说,在递归调用中,系统或者编译器的优化功能不够好的化,在这个栈上可能会消耗很多空间,这个时候如果你把程序改成非递归的形式,然后再用动态分配技术分配栈可能就会把程序的性能提高一大块-这也是我们学习这门技术的意义之一,因为系统是机械化的,你如果知道更好的优化办法,为什么不用呢? 什么时候可以用递归解决问题?到了这一步,如果你对于上面说的已经相当明白的话,这个问题不难回答,如果我们要解决的问题要分成几个小的部分,而其中的一些与你要解决的问题是一样的,只不过是问题的规模(如参数等)小了,那么这样的问题可以用递归来解决.根据问题设计好一个递归是所有这些的基础,转换也是在原来的递归程序上进行的,所以这一步一定要做好.通常,设计一个递归程序要注意一下几个问题:a)可以递归解决的问题是什么?b)入口和出口参数是什么-即要明确好出入的接口。 说白了，递归程序是在对所要解决的问题进行数学上的分析后给出的，也就是说递归算法是从纯数学的角度出 发考虑的，而非递归的算法则是在递归算法的基础上考虑计算机内部处理递归程序的机制考虑来实现转换的。任何一个递归算法，只要能够准确的写出递归调用树的情况，分析清楚对当前结点的访问操作是什么，左子树右子树是什么那么实现起递归和非递归的转换就很轻松了。参考文献：1 张益新、沈雁编：算法导论，国防科大出版社。 2 严蔚敏：数据结构，清华大学出版社。3 徐孝凯：数据结构，清华大学出版社2006年9月第2版。recursive algorithm design and conversion of non-recursivesun qing-yu abstract: the algorithm design recursive and non recursive conversion is the basis for learning algorithm design, skilled use of recursive and non recursive conversion is the basis for algorithm design in this paper i will introduce several algorithm design recursive and non recursive conversion method. so that we can better achieve the recursive algorithm desig