2022年递归算法与非递归算法的转换分享 .pdf

《2022年递归算法与非递归算法的转换分享 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法与非递归算法的转换分享 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归算法与非递归算法的转摘要：递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过 程)来表示问题的解。 递归的效率一般不高，但是递归比较符合人类的思维方式。 一般而言非递归算法更有效；但很多时候递归算法容易实现，编程简单。关键字： 递归算法非递归算法转换引言：递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率比较差。因此，在求解某些问题时， 通常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。1.

2、递归算法1.1 什么是递归算法递归过程一般通过函数或子过程来实现。递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。1.2 递归算法的特点递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中， 递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时， 必须有一个明确的递归结束条件， 称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储

3、。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。1.3 递归算法要求递归算法所体现的 “ 重复” 一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半 )；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解

4、答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。2非递归算法2.1什么是非递归算法非递归算法是采用循环或者栈的方式来实现2.2非递归算法的特点递归算法递归越深，占用栈空间也就越多，相对而言，非递归占用的栈空间少。效率比较高2.3非递归算法的用例int _q(int n,int m) int sum=0; Point tmp(n,m); s.push (tmp); while(!s.empty() n=tmp.n; m=tmp.m; s.pop(); if(n1) | (m0) +sum; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

5、 - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - else if(n=1) |(m=1) +sum; else if(nm) s.push(Point(n,n); else if(n=m) +sum; s.push(Point(n,m-1); else s.push(Point(n,m-1); s.push(Point(n-m,m); int main() int num; unsigned int p; docoutnum; p=clock(); cout非递归：couttt 用时:clock()-pendlendl;

6、 return 0; 3递归和非递归的转换3.1转换方法将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值， 需要回溯。 前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法。3.1.1直接转换法直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。尾递归是指在递归算法中， 递归调用语句只有一个， 而且是处在算法的最后。当递归调用返回时， 是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处， 所以，不必利用栈来保存返回信息。对于尾递归形式的递归名师资料总结 - - -精品资料欢迎下载 - - -

7、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 算法，可以利用循环结构来替代。对于单向递归， 可以设置一些变量保存中间结构，将递归结构用循环结构来替代。3.1.2间接转换法使用栈保存中间结果，一般需要根据递归函数在执行过程中栈的变化得到。间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等。4总结非递归算法， 也用到栈函数了， 和递归没多大区别，每次递归进栈出栈，非递归算法的每次调用栈函数也是进栈出栈。主要是在非递归算法中，它的栈函数里比递归多了些赋值语句，所以效率上，非递归比递归差。只不过，递归越深，占用栈空间越多。非递归算法，占用的栈空间少。如果，递归的深度还没达到超出栈空间的程度，那么递归比非递归好。参考文献：算法导论国防科大出版社张益新沈雁编著数据结构清华大学出版设严敏华编著计算机算法设计与分析电子工业出版社王晓东编著名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -