首页 > 编程语言 > 详细

递归算法

时间:2019-05-24 15:52:20      阅读:69      评论:0      收藏:0      [点我收藏+]

  递归在算法中非常常见,可以让方法调用自己,比如二分查找法就可以用递归的方法来实现。不过笔者之前从来没有看过递归的规范,今天在翻阅算法第四版时,看到了一个编写递归代码的原则,特分享一下。

  1.递归总有一个最简单的情况——方法的第一条语句总是一个包含return的条件语句;

  2.递归总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况。

  3.递归调用的父问题和尝试解决的子问题之间不应该有交集。

 


  下面贴一段自己以前写的二分查找法的递归实现好了。当个反例,没有按照规范来写,XD。

package algorithm;

public class BinarySearch_Rec {
    //定义一个arr数组,需要查询值a在数组中的位置key
    public int binarySearch(int a, int low, int high, int[] arr) {
        //定义binary search中值mid
        if(high>=low){
            int mid=(high+low)/2;
            if(a==arr[mid]){
                return mid;
            }else if(a>arr[mid]){
                return (binarySearch(a,mid+1,high,arr));
            }else {
                return (binarySearch(a,low,mid-1,arr));
            }
        }else {
            return -1;
        }
    }

    public static void main(String[] args) throws Exception {
        int[] arr = new int[]{123, 243, 534, 645, 126, 541, 64, 65};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(arr);
        BinarySearch_Rec binarySearchRec = new BinarySearch_Rec();
        int key = binarySearchRec.binarySearch(645, 0, arr.length, arr);
        bubbleSort.output(arr);
        System.out.println(key+1);
    }
}

 

递归算法

原文:https://www.cnblogs.com/CNty/p/10918069.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!