递归程序转换成非递归程序的方法分析+源代码
时间:2018-12-11 21:44 来源:毕业论文 作者:毕业论文 点击:次
| 改程序用于计算递归程序与非递归程序在遍历节点为3、7、15、31、63、127、255的二叉树时所用的时间。 （1）用vc6.0打开程序，并运行程序 （2）按照菜单选择节点数对应的数字，点击回车； （3）按照菜单选择前序递归、中序递归、后序递归、前序非递归、中序非递归、后序非递归程序，点击回车； （4）点击回车，重复（2）和（3）； 摘要 递归方法在数学和计算机中都有很广泛的应用,但是递归算法存在语言限制,运行效率低等问题,有时需要将其转化成非递归算法.如何转换成非递归算法常常是人们困惑的问题.因此本文主要通过对递归方法分类,给出不同类型的递归算法转化成非递归算法的编程规则、方法,以及采用递归算法和非递归算法的时机.通过算法分析给出具体的求解方法,并在windows7.0上运行程序获得具体实验数据进行比较.31439 毕业论文关键词 递归程序;非递归程序;栈;算法 1引言 递归(recursion)是一种重要的数学方法,它通常是把一个复杂的大问题变成一个类似于原始问题的小规模问题[1].它是指一个进程在其界定的程序中有直接或间接调用本身的一种方式.在计算机中,程序调用本身编程技术称为递归算法.递归程序是目前应用最广泛的编程语言之一,在很少的算法下便可解决程序中的多次重复,大大地削减了程序中的代码.但是递归算法在运行时效率往往较低,需要将其转化为相应的非递归算法.递归算法的非递归化往往很困难,因此本文给出递归算法非递归化的方法.另外由于两种算法皆有优越性,所以通过算法分析比较,给出相应问题的策略. 2递归的相关定义 递归是指在设计算法程序时,出现多次调用程序中的过程或函数.递归不光是数学中的重要概念,亦是计算技术中重要的概念.在计算机领域里,递归程序涉及到的概念包括[4]: （1）递归关系:一个数列的若干个连续项之间的关系. （2）递归数列:根据递归关系确定的相关数列. （3）递归过程:直接或间接调用自身的过程. （4）递归算法:包含递归过程的算法. （5）递归程序:直接或间接调用本身程序的算法. 3 递归设计方法 递归的方法是指在有限的步骤下,根据一定的准则或计算公式对一个或多个特定元素的公式运算,以确定一系列元素（如方法或函数）.递归程序一般分成两类[2]：直接递归和间接递归.若程序中有调用自身的过程,称之为直接递归;若过程或函数m与过程或函数n互相调用,称之为间接递归.递归算法主要用于解决三大类问题: (1) 用于解决问题的程序可以按递归的形式定义.（Fibonacci函数） (2) 可以用递归算法实现的问题.（回溯） (3) 基于递归定义的数据结构（树的遍历,图的搜索） 递归设计需要先判断,所求问题是否适合使用递归程序并确定其递归模型,在此基础上,我们还需要懂得实现递归非递归化的方法.下面我们先来看看什么是递归模型,递归算法的设计过程,递归的分类以及优缺点. 3.1 递归模型 递归模型反映一个递归问题的递归结构[3].下面这样一个需要使用多次迭代方法来解决的问题: 它的递归模型如下: 在这个模型中,式子（1）给出了递归的终止的条件,而式子（2）则给出了fun(n)与fun(n-1)和fun(n-2)的值得关系. 3.2递归算法设计 在这给出这样一个小故事来帮助大家理解递归函数设计的一般思文过程.“山上有一座庙,而庙里有一个老和尚,老和尚在讲故事,他所讲的故事是:上山有一座庙,而庙里有一个老和尚,老和尚在讲故事,他所讲的故事是:……”这个故事中就包含了本身——自己调用自己.如果现在我们将这个故事改装成一个函数 (责任编辑：qin) |