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