数据结构与算法（JAVA篇）之递归算法（二）

/**
 *
 * @author SunnyMoon
 */

/**
 * 概念介绍:
 * 
 * 递归的二分查找: 想用最少的比较次数在一个有序的数组中找到一个给定的数据项。
 * 
 * 非递归的二分查找：二分查找也可以用非递归的算法，但是分治算法通常要回到递归。分治算
 *                  法常常是一个方法，在这个方法中含有两个对自身的递归的调用。
 * 
 * 分治算法：递归的二分查找是分治算法的一种实现方法。把一个是问题分成两个更小的问题，
 *          并且解决它们。这个过程一直持续下去直到易于求解的基值情况，就不需再分了。
 *          分治算法常常是一上方法，在这个方法中含有两个对自身的递归调用，分别对应于
 *          问题的两个部分。在二分查找中，就有两个这样的调用，但是只有一个真的执行了
 *          （调用哪一个取决于关键字的值）。        
 * 递归的效率：调用一个方法会有一定的代价和开销。首先，控制必须须从当前位置转移到调用
 *            方法的开始处。其次，传给这个方法的参数以及这个方法返回地址都要初压到一
 *            个栈里，为的是方法能够访问参数以及知道返回值在存储在哪里，这个过程也称
 *            "保存现场"。递归方法的使用的本质是从概念上简化了问题，而不是因为它更有
 *            效率。当使用递归的效率很低的时候，就可以考虑如果把递归转化成非递归。
 */
class OrdArray {

    private long[] a;
    private int nElems;

    public OrdArray(int max) {
        a = new long[max];
        nElems = 0;
    }

    public int size() {
        return nElems;
    }

    public int find(long searchKey) {
        return recFind(searchKey, 0, nElems - 1);//调用递归方法
        //return recFind2(searchKey, 0, nElems - 1);//调用非递归方法
    }

    public int recFind(long searchKey, int lowerBound, int upperBound) {//递归方法定义
        int curIn = (lowerBound + upperBound) / 2;
        if (a[curIn] == searchKey) {
            return curIn;
        } else if (lowerBound > upperBound) {
            return nElems;
        } else {
            if (a[curIn] < searchKey) {
                return recFind(searchKey, curIn + 1, upperBound);
            } else {
                return recFind(searchKey, lowerBound, curIn - 1);
            }
        }
    }
    public int recFind2(long searchKey, int lowerBound, int upperBound){//非递归方法定义
        int curIn=0;
        
        while(true){
            curIn=(lowerBound+upperBound)/2;
            if(a[curIn]==searchKey)
                return curIn;
            else if(lowerBound>upperBound)
                return nElems;
            else{
                if(a[curIn]<searchKey){
                    lowerBound=curIn+1;
                }
                else{
                    upperBound=curIn-1;
                }
            }
        }
    }
    public void insert(long value){
        int j;
        for(j=0; j<nElems; j++)
            if(a[j]>value)
                break;
        for(int k=nElems; k>j; k--)
                a[k]=a[k-1];
                a[j]=value;
                nElems++;
    }
    public void display(){
        for(int j=0; j<nElems; j++){
            System.out.println(a[j]+"");
        }
    }
}
class BinarySearchApp{
    public static void main(String[] args){
        int maxSize=100;
        OrdArray arr=new OrdArray(maxSize);
        
        arr.insert(72);
        arr.insert(90);
        arr.insert(45);
        arr.insert(126);
        arr.insert(54);
        arr.insert(99);
        arr.insert(144);
        arr.insert(27);
        arr.insert(135);
        arr.insert(81);
        arr.insert(18);
        arr.insert(100);
        arr.insert(9);
        arr.insert(117);
        arr.insert(63);
        arr.insert(36);
        arr.display();
        
        int searchKey=100;
        if(arr.find(searchKey) !=arr.size())
            System.out.println("Found "+searchKey);
        else
            System.out.println("Can't find "+ searchKey);
    }
}
/**
 * 运行结果：
 * 9
 * 18
 * 27
 * 36
 * 45
 * 54
 * 63
 * 72
 * 81
 * 90
 * 99
 * 100
 * 117
 * 126
 * 135
 * 144
 * Found 100
 */
/**
 * 总结：
 * 很多的数学问题都使用递归的方法解决，比如找两个数的最大公约数，求一个数的
 * 乘方等等。如果有效率需求的时候，可以再考虑将递归转化成非递归。
 */

 

评论

2 楼 sunnymoon 2008-11-25  

zhanglubing927 写道

我也来写一个关于递归的. (前几天的笔试题,不知道当时写对没,下来完成了它.)


Java代码

package com.jason.exam;   
  
/**  
 * 杨辉三角  
 *  
 * @author Jason Zhang  
 *  
 */  
public class YangHuiTriangle {   
    /**  
     * 根据位置获得杨辉数  
     *  
     * @param m 行数  
     * @param n 列数  
     * @return 所在行列的杨辉数  
     */  
    private static int YangHuiNumber(int m, int n) {   
        if (m == 0 || n == 0)   
            return 1;   
        if (n > m / 2)   
            return YangHuiNumber(m, m - n);   
        return YangHuiNumber(m - 1, n - 1) + YangHuiNumber(m - 1, n);   
    }   
  
    public static void main(String[] args) {   
        int N = 10;   
        for (int m = 0; m < N; m++) {   
            for (int n = 0; n <= m; n++) {   
                System.out.print(YangHuiNumber(m, n) + " ");   
            }   
            System.out.println();   
        }   
    }   
}  package com.jason.exam;

/**
* 杨辉三角
*
* @author Jason Zhang
*
*/
public class YangHuiTriangle {
    /**
     * 根据位置获得杨辉数
     *
     * @param m 行数
     * @param n 列数
     * @return 所在行列的杨辉数
     */
    private static int YangHuiNumber(int m, int n) {
        if (m == 0 || n == 0)
            return 1;
        if (n > m / 2)
            return YangHuiNumber(m, m - n);
        return YangHuiNumber(m - 1, n - 1) + YangHuiNumber(m - 1, n);
    }

    public static void main(String[] args) {
        int N = 10;
        for (int m = 0; m < N; m++) {
            for (int n = 0; n <= m; n++) {
                System.out.print(YangHuiNumber(m, n) + " ");
            }
            System.out.println();
        }
    }
}
这个是不是性能不好,因为每一个数字都通过计算才得出的. 比如我求YangHuiNumber(100,20),我需要计算前面所有的数字 而实际上前面已经得到了过YangHuiNumber(99,19)和YangHuiNumber(99,20). 没必要再计算他们...

提两个见意：
1. 你的递归实现存在问题。应该研究一下递归是什么样子的再来写。
2. 编码规则上来看，当为常量时才写成大写。（int N = 10;）

1 楼 zhanglubing927 2008-11-25  

我也来写一个关于递归的.
(前几天的笔试题,不知道当时写对没,下来完成了它.)

package com.jason.exam;

/**
 * 杨辉三角
 *
 * @author Jason Zhang
 *
 */
public class YangHuiTriangle {
    /**
     * 根据位置获得杨辉数
     *
     * @param m 行数
     * @param n 列数
     * @return 所在行列的杨辉数
     */
    private static int YangHuiNumber(int m, int n) {
        if (m == 0 || n == 0)
            return 1;
        if (n > m / 2)
            return YangHuiNumber(m, m - n);
        return YangHuiNumber(m - 1, n - 1) + YangHuiNumber(m - 1, n);
    }

    public static void main(String[] args) {
        int N = 10;
        for (int m = 0; m < N; m++) {
            for (int n = 0; n <= m; n++) {
                System.out.print(YangHuiNumber(m, n) + " ");
            }
            System.out.println();
        }
    }
}

这个是不是性能不好,因为每一个数字都通过计算才得出的.
比如我求YangHuiNumber(100,20),我需要计算前面所有的数字
而实际上前面已经得到了过YangHuiNumber(99,19)和YangHuiNumber(99,20).
没必要再计算他们...