- 递归的概念
方法调用自己就是递归，我们可以采用数学归纳法来证明递归的正确性。 - 编写递归代码时需要注意以下三点
1、递归总有一个最简单的情况，方法的第一句总是一个包含return的条件语句。也就是说第一句就是递归出口。
2、递归调用总是尝试去解决一个规模更小的问题，这样递归才能收敛到最简单的情况。
3、递归调用的子问题不能有交集。 - 代码示例
package com.test.recursion;
/**
* 测试二分查找
*/
public class TestBinarySearch {
/**
* 从数组中找出key的下标，如果不存在返回-1
*
* @param key
* @param a
* @return
*/
public static int search(int key, int[] a) {
return search(key, a, 0, a.length - 1);
}
/**
* 递归版二分查找
* @param key
* @param a
* @param lo
* @param hi
* @return
*/
private static int search(int key, int[] a, int lo, int hi) {
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key > a[mid]) return search(key, a, mid + 1, hi);
else if (key < a[mid]) return search(key, a, lo, mid - 1);
else return mid;
}
/**
* 主函数
* @param args
*/
public static void main(String[] args) {
int[] a = {1, 4, 7, 9};
int index = search(1, a);
System.out.println(index);
}
}
违背其中任意一条都可能得到错误的结果或者低效的代码，而坚持这三个原则能写出清晰、正确、易评估的程序。
