`

Java将递归改成循环的通用方法

 
阅读更多
用Stack或LinkedList来实现内存中的出栈入栈过程,即可将递归改成循环。

正式开始前先厘清几个概念:
循环(loop) - 最基础的概念, 所有重复的行为
递归(recursion) - 在函数内调用自身, 将复杂情况逐步转化成基本情况
(数学)迭代(iterate) - 在多次循环中逐步接近结果
(编程)迭代(iterate) - 按顺序访问线性结构中的每一项
遍历(traversal) - 按规则访问非线性结构中的每一项
确切地说,递归也属于循环。下文中的「循环」特指非递归的循环。

第一个例子用求阶乘,顺便加了迭代方法。
[java] view plain copy
import java.util.Stack;  
  
public class Factorial{  
    public static void main(String[] args){  
        Factorial f = new Factorial();  
        System.out.println(f.recursion(5));  
        System.out.println(f.loop(5));  
        System.out.println(f.iteration(5));  
    }  
  
    /** 
     * 递归求阶乘 
     */  
    public int recursion(int n){  
        if (n == 1) return 1;  
        return recursion(n-1) * n;  
    }  
  
    /** 
     * 循环求阶乘 
     */  
    public int loop(int n){  
        Stack<Integer> stack = new Stack<Integer>();  
        int result = 1;  
        stack.push(n);  
        while(!stack.isEmpty()){  
            n = stack.pop();  
            result *= n;  
            if (n > 1) stack.push(n-1);  
        }  
        return result;  
    }  
  
    /** 
     * 迭代求阶乘 
     */  
    public int iteration(int n){  
        int result = 1;  
        for(int i = 1; i <= n; i++){  
            result *= i;  
        }  
        return result;  
    }  
}  


第二个例子是快速排序。递归快排大量数量时,容易爆栈。这时可以改成循环。
[java] view plain copy
import java.util.Random;  
  
public class Sorts{  
    private static Random rand = new Random();  
  
    public static void main(String[] args){  
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62  
            ,99,98,54,56,17,18,23,34,15,35,25,53,51};   
        quickSort(a);  
        System.out.println(Arrays.toString(a));  
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62  
            ,99,98,54,56,17,18,23,34,15,35,25,53,51};   
        quickSortByLoop(a);  
        System.out.println(Arrays.toString(a));  
    }  
  
    /** 
     * 快速排序 
     * 递归实现 
     */  
    private static void quickSort(int[] arr, int start, int end){  
        if (start >= end) return;  
        int base = arr[start + rand.nextInt(end-start+1)]; //中轴值  
        int left = start, right = end; //指示左右两端未排序的边界索引  
        int i = start; // 用于排序  
        while(i <= right){  
            if (arr[i] < base){ //小于中轴值则移到左侧  
                swap(arr, left++, i++);  
            }else if (arr[i] > base){ //大于中轴值则移到右侧  
                swap(arr, right--, i); //当前i位置的值未排序,故i不自增  
            }else{  
                i++;  
            }  
        }  
        //排完后left左侧均为小于base的数,right右侧均为大于base的数  
        quickSort(arr, start, left-1);  
        quickSort(arr, right+1, end);  
    }  
  
  
    /** 
     * 快速排序 
     * 循环实现 
     */  
    private static quickSortByLoop(int[] arr){  
        Stack<Integer> stack = new Stack<Integer>();  
        int start = 0;  
        int end = arr.length - 1;  
        stack.push(start);  
        stack.push(end);  
        while(!stack.isEmpty()){  
            end = stack.pop(); // 顺序很重要  
            start = stack.pop();  
            if (start < end){ // 开始排序  
                int i = start;  
                int base = arr[start + rand.nextInt(end-start+1)]  
                int left = start;  
                int right = end;  
                while(i <= right){  
                    if (arr[i] < base){  
                        swap(arr, left++, i++);  
                    }else if (arr[i] > base){  
                        swap(arr, right--, i);  
                    }else {  
                        i++;  
                    }  
                }  
                // ----右半边----  
                stack.push(right + 1);  
                stack.push(end);  
                // ----左半边----  
                stack.push(start);  
                stack.push(left - 1);  
            }  
        }  
    }  
}  

 

分享到:
评论

相关推荐

    java递归树型结构通用数据库

    "Java递归树型结构通用数据库" Java递归树型结构通用数据库是指使用Java语言实现的递归树型结构数据库系统,该系统可以实现树型结构的部门管理,包括部门的添加、删除、修改和查询等操作。 知识点: 1. 递归树型...

    Java中递归逻辑循环调用解压zip里面所有的压缩包

    Java中递归逻辑循环调用解压zip里面所有的压缩包 Java中递归逻辑循环调用解压zip里面所有的压缩包

    Java 跳出递归循环问题解决办法

    下面将详细讨论两种常见的方法来解决Java中的跳出递归循环问题。 **1. 使用标志(Flag)** 一个常见的方法是通过设置一个全局变量或类成员变量作为递归的退出标志。当满足特定条件时,改变这个标志,递归函数在...

    用Java集合递归实现通用树Tree

    本资源主要关注如何使用Java集合框架来递归实现一个通用的树结构,即`Tree`。下面我们将深入探讨这个主题。 首先,我们要了解Java集合框架。Java集合框架是Java语言提供的一组接口和类,用于存储和操作各种数据结构...

    Java SE程序 递归 Java SE程序 递归

    Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE...

    JavaScript的递归之递归与循环示例介绍

    递归与循环 对于不同类型的需要重复计算的问题,循环和递归两种方法各有所长,能给出更直观简单的方案。另一方面,循环和递归的方法可以互相转换。任何一个循环的代码都可以用递归改写,实现相同的功能;反之亦然。...

    java递归无限层级树

    例如,如果一个节点在某个条件下应有子节点,我们就在其`children`集合中添加新的`TreeNode`对象,并递归调用同一个方法,将层级加一。 ```java public void generateTree(TreeNode parent, int level) { if (满足...

    java 用递归实现字符串反转

    在Java编程语言中,递归是一种常用的方法来解决许多问题,特别是那些可以通过分解成更小子问题来解决的问题。本文将详细介绍如何使用递归来实现字符串的反转。 #### 一、递归基础概念 递归是指在函数或方法的定义...

    (java递归)删除文件

    在本文中,我们将深入探讨如何使用递归方法在Java中删除文件,这通常涉及到目录及其包含的所有文件和子目录的删除。以下是根据提供的代码片段提炼出的关键知识点: ### 关键知识点一:递归函数设计 递归函数`find...

    jsp jstl 递归 输出树 Tree 后台 Java 集合 递归 实现通用 树Tree

    本主题将深入探讨如何使用Java集合、JSP和JSTL来递归地创建并输出树形结构(Tree),特别是用于前端展示。 首先,我们要理解Java集合在构建树结构中的作用。在Java中,可以使用ArrayList、LinkedList或者自定义的...

    java 八皇后循环递归回溯实现

    经典的八皇后问题,我看过很多解决八皇后的方法,这个是最好理解的,简单又清楚。

    java实现递归调用

    本篇文章将详细介绍如何使用Java实现递归调用来遍历一棵树,并结合SQL代码进行说明。 首先,我们需要理解树的基本概念。树是一种非线性的数据结构,由节点(或称为顶点)和边组成。每个节点可以有零个或多个子节点...

    Java递归算法构造JSON树形结构

    Java 递归算法构造 JSON 树形结构是指通过 Java 语言使用递归算法将数据库中的菜单表构建成树形的 JSON 格式发送给第三方。这种方法可以将复杂的树形结构数据转换成易于理解和处理的 JSON 格式。 在 Java 中,使用...

    java中递归用法详解

    java中递归的用法比较单一,但是用途比较重要,在开发中经常用到,熟练掌握递归的用法有利于程序代码的快速合理编写

    Java 递归法求5!阶乘相加之和.rar

    Java 采取递归方法求5!的阶乘,递归方法求阶乘之和,输入要阶乘的数字,递归公式:fn=fn_1*4! 具体来看以下代码:  System.out.print("输入要阶乘的数字:");  Scanner scanner = new Scanner(System.in);  int n ...

    java 中的经典递归

    本节将通过一个具体的Java代码示例来详细介绍递归的应用,该示例实现了字符数组的全排列问题。 ```java public class AllSort { public static void main(String[] args) { char buf[] = {'a', 'b', 'c'}; perm...

    java详细讲解递归

    2. **递归步骤**(Recursive Step):这是递归方法如何将问题分解为更小规模子问题的过程,并且最终通过这些子问题的解决方案来构建出原始问题的解决方案。 #### 三、递归示例分析 接下来,我们将基于给定的部分...

    Java递归将List转为树形结构Java递归将List转为树形结构

    Java递归将List转为树形结构 博客地址:https://blog.csdn.net/weixin_38500202/article/details/110456363

    java编写的递归与非递归

    在Java编程中,递归和非递归是两种常用的处理问题的方法。递归通常用于解决那些可以通过分解为更小问题来解决的问题,而非递归则更适合于使用迭代的方式来解决问题。下面将详细介绍这两种方法,并通过计算阶乘的例子...

Global site tag (gtag.js) - Google Analytics