Java数据结构和算法之递归
2020-11-28 05:27
标签：class java ext c int com 四、递归 递归是函数调用自身的一种特殊的编程技术，其应用主要在以下几个方面： 阶乘 在java当中的基本形式是： Public void mothed（int n）{//当满足某条件时： Mothed（n‐1）； } 递归二分查找 Java二分查找实现,欢迎大家提出交流意见. /** *名称:BinarySearch *功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: *
1、要求所查找的数组已有序,并且其中元素已实现Comparable * 2、非递归查找使用search();,递归查找使用searchRecursively();
* *本程序仅供编程学习参考 * *@author: Winty *@date: 2008-8-11 *@email:
[email]wintys@gmail.com[/email] */ class BinarySearch private T[] data;//要排序的数据 public BinarySearch(T[] data){ this.data = data; } public int search(T key){ int low; int high; int mid; if(data == null){ return -1; } low = 0; high = data.length - 1; while(low
mid = (low +high) / 2; System.out.println("mid " + mid + " mid value:" +
datamid]);/// if(key.compareTo(data[mid])
high = mid - 1; }else if(key.compareTo(data[mid]) > 0){ low = mid + 1; }else if(key.compareTo(data[mid]) == 0){ return mid; } } return -1; } private int doSearchRecursively(int low , int high , T key){
int mid; int result; if(low
mid = (low + high) / 2; result =
key.compareTo(data[mid]); System.out.println("mid " + mid + " mid value:" +
data[mid]);/// if(result
return doSearchRecursively(low , mid - 1 , key);
}else if(result > 0){
return doSearchRecursively(mid + 1 , high ,
key);
}else if(result ==
0){
return mid; } } return -1; } public int searchRecursively(T key){ if(data ==null)return -1;
return doSearchRecursively(0 , data.length - 1 , key); } public static void main(String[] args){ Integer[] data = {1 ,4 ,5 ,8 ,15 ,33,48 ,77
,96}; BinarySearch System.out.println("Key index:" + binSearch.searchRecursively(3) );
//String [] dataStr = {"A" ,"C" ,"F" ,"J" ,"L" ,"N" ,"T"};
//BinarySearch //System.out.println("Key index:" + binSearch.search("A") );
} } 递归排序 其实在数组的全排序中完全可以使用更加易懂简便的写法——for循环，但是通过for循环编写数组全排序需要有一个先决条件——知道数组全排序的个数，因为有n个数据全排序就需要写n个嵌套for循环。因此在写全排序时一般使用递归方法。这就是我的第一个关于递归排序的见解——递归排序可以无需已知排序数组的长度，即排序个数！
其二，不管是使用递归进行数组排序还是使用for循环进行数组的排序，它们都是本质都是使用枚举，因此可以得出这样一个结论:枚举可以确保找出每一种可能的排序规则！
其三，枚举是列出所有的方法并找出符合要求的算法，因此其算法效率一定比较的低，需要对其进行优化，才能达到较好的效果（递归的时候排除所有不可能的方案） 消除递归 消除递归的基本思路是用栈来模拟系统的函数调用从而消除递归。基本上要做以下三件事： 传递参数（包括返回地址）并转到函数入口； 获得参数并处理参数； 根据传入的返回地址； 返回 Java数据结构和算法之递归,搜素材,soscw.com Java数据结构和算法之递归 标签：class java ext c int com 原文地址：http://www.cnblogs.com/amirsterry/p/3704172.html
上一篇：Java中Integer类的方法
下一篇：java中抽象类与接口的区别