遞歸

厶汀 2013-10-25

展開全文

遞歸是函數(shù)調(diào)用自身的一種特殊的編程技術(shù)，其應(yīng)用主要在以下幾個方面：

階乘

在java當中的基本形式是：Public void mothed（int n）{//當滿足某條件時：

Mothed（n-1）；

}

遞歸二分查找

Java二分查找實現(xiàn),歡迎大家提出交流意見.

/**
*名稱:BinarySearch
*功能:實現(xiàn)了折半查找(二分查找)的遞歸和非遞歸算法.
*說明:
*     1、要求所查找的數(shù)組已有序,并且其中元素已實現(xiàn)Comparable<T>接口,如Integer、String等.
*    2、非遞歸查找使用search();,遞歸查找使用searchRecursively();
*
*本程序僅供編程學(xué)習(xí)參考
*
*@author:   Winty
*@date:     2008-8-11
*@email:    [email]wintys@gmail.com[/email]
*/

class BinarySearch<T extends Comparable<T>> {
    private T[]  data;//要排序的數(shù)據(jù)

    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 <= high){
            mid = (low + high) / 2;
            System.out.println("mid " + mid + " mid value:" + data[mid]);///

            if(key.compareTo(data[mid]) < 0){
                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 <= high){
            mid = (low + high) / 2;
            result = key.compareTo(data[mid]);
            System.out.println("mid " + mid + " mid value:" + data[mid]);///

            if(result < 0){
                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<Integer> binSearch = new BinarySearch<Integer>(data);
        //System.out.println("Key index:" + binSearch.search(33) );

        System.out.println("Key index:" + binSearch.searchRecursively(3) );

        //String [] dataStr = {"A" ,"C" ,"F" ,"J" ,"L" ,"N" ,"T"};
        //BinarySearch<String> binSearch = new BinarySearch<String>(dataStr);
        //System.out.println("Key index:" + binSearch.search("A") );
    }
}

遞歸排序

其實在數(shù)組的全排序中完全可以使用更加易懂簡便的寫法——for循環(huán)，但是通過for循環(huán)編寫數(shù)組全排序需要有一個先決條件——知道數(shù)組全排序的個數(shù)，因為有n個數(shù)據(jù)全排序就需要寫n個嵌套for循環(huán)。因此在寫全排序時一般使用遞歸方法。這就是我的第一個關(guān)于遞歸排序的見解——遞歸排序可以無需已知排序數(shù)組的長度，即排序個數(shù)！

其二，不管是使用遞歸進行數(shù)組排序還是使用for循環(huán)進行數(shù)組的排序，它們都是本質(zhì)都是使用枚舉，因此可以得出這樣一個結(jié)論:枚舉可以確保找出每一種可能的排序規(guī)則！