文件名称:
数据结构与算法（JAVA篇）之递归算法
开发工具:
文件大小: 5kb
下载次数: 0
上传时间: 2008-11-26
详细说明： /** * * @author SunnyMoon */ ////////////////////////////////////////////////////////////////////////////// /** * 概念介绍： * * 消除递归： * 一个算法作为一个递归的方法通常从概念上很容易理解，但实际使用中递归的效率不高，在这种 * 情况下，把递归算法转换成非递归的算法是非常有用的，这种转换经常用到栈。 * * 递归和栈： * 递归和栈之间有着紧密的联系，大部分的编译器使用栈实现递归的。 * * 调用方法的时候发生什么： * 1. 编译器会把这个方法所有当前参数及返回地址压入栈中； * 2. 将控制权交给这个方法，方法通过获得栈顶元素值访问参数； * 3. 方法运行结束的时候，值退栈，参数消失且控制权重新回到返回地址； * * 模拟递归方法： * 可以将任意一个递归方法转换为非递归的基于栈的方法。在一些简单的情况可以完全消除栈，只 * 使用一个简单的循环，但是在很复杂的情况，算法中必须须要保留栈。本 例子是简单的情况，可 * 以进一步完全消除栈。 */ ///////////////////////////////////////////////////////////////////////////// /** * 计算三角数字的问题: * 递归算法描述如下 * int triiangle(int n){ * if(n==1) * return 1; * else * return (n+triangle(n-1)); * } */ import java.io.*; /** * 模拟一个递归方法，通用的方式消除递归 */ class Params {//封装了方法的返回地址和方法的参数 public int number; public int returnAddress; public Params(int num, int returnAdd) { number = num; returnAddress = returnAdd; } } class StackX {//模拟递归时使用的栈 private int maxSize; private Params[] stackArray; private int top; public StackX(int s) { maxSize = s; stackArray = new Params[maxSize]; top = -1; } public void push(Params p) { stackArray[++top] = p; } public Params pop() { return stackArray[top--]; } public Params peek() { return stackArray[top]; } } class StackTriangleApp { static int theNumber; static int theAnswer; static StackX theStack; static int logicAddress; static Params theseParams; public static void main(String[] args) throws IOException{//主方法 System.out.print("Number = "); theNumber = getInt(); stackTriangle(); System.out.println(""); System.out.println("Trriangle = " + theAnswer); } @SuppressWarnings("empty-statement") public static void stackTriangle() {//计算三角数字的方法，模拟递归方法 theStack = new StackX(100); logicAddress = 1;//设置一个逻辑地址为入口地址 while (step() == false); } public static boolean step() { switch (logicAddress) { case 1: theseParams = new Params(theNumber, 6);//设定循环返回的地址 theStack.push(theseParams); logicAddress = 2; break; case 2: theseParams = theStack.peek(); if (theseParams.number == 1) { theAnswer = 1; logicAddress = 5; } else { logicAddress = 3; } break; case 3: Params newParams = new Params(theseParams.number - 1, 4); theStack.push(newParams); logicAddress = 2; break; case 4: theseParams = theStack.peek(); theAnswer = theAnswer + theseParams.number; logicAddress = 5; break; case 5: theseParams = theStack.peek(); logicAddress = theseParams.returnAddress; theStack.pop(); break; case 6: return true; } return false; } public static String getString() throws IOException{ InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } public static int getInt() throws IOException{ String s=getString(); return Integer.parseInt(s); } } /** * 总结： * 当要求效率的时候可以把弟归转化为基于栈的非递归，进而可以把基于栈的转化为仅有循环的 * 非递归，这种情况下效率是最高的。 * 但是一些复杂的情况可以转化为基于栈的非递归，但是无法消除栈的。 * 一些递归的算法是非常优秀的，比如分治算法。 */ ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
