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

　　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);    }}

　　 对了，测试类里用了冒泡排序来给数组排序，否则二分查找法无法查找无序数组，笔者之前忘了，这里把冒泡排序的实现也贴一下好了（实际上是我懒得改代码用Array.sort()方法了，xd)

1 package algorithm; 2  3 public class BubbleSort { 4     public void bubbleSort(int[] arr) { 5         for (int x = 0; x < arr.length; x++) { 6             for (int y = 0; y < arr.length - 1; y++) { 7                 if (arr[y] > arr[y + 1]) { 8                     int index; 9                     index = arr[y];10                     arr[y] = arr[y + 1];11                     arr[y + 1] = index;12                 }13             }14         }15     }16 }