编写递归代码时需要考虑待解决问题是否符合以下三个特点:
1.递归总有一个最简单的情况—方法的第一条语句总是一个包含return的条件语句.
2.递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况.
3.递归调用的父问题和尝试解决的子问题之间不应该有交集
下面通过二分查找的递归写法为例讲解:
先看下二分法的普通写法
public static int binarySearch(int key, int[] arr) {
//头尾的索引
int minIndex = 0;
int maxIndex = arr.length - 1;
while (true) {
//当minIndex > maxIndex说明待查找的数不存在
if (minIndex > maxIndex) {
return -1;
}
//每循环一次midIndex都要折半
int midIndex = minIndex + (maxIndex - minIndex) / 2;
//这里是重点,本来就应该是这种写法,int midIndex=(maxIndex - minIndex) / 2 只是因为在初始化的时候minIndex=0所以省掉了
//根据条件移动头尾光标,如果正好相等则直接返回
if (key < arr[midIndex]) {
maxIndex = midIndex - 1;
} else if (key > arr[midIndex]) {
minIndex = midIndex + 1;
} else {
return midIndex;
}
}
}
测试代码
public static void main(String[] args) {
int[] arr = {1, 3, 6, 9, 11, 33, 55, 77};
int index = binarySearch(11, arr);
System.out.println("index:"+index);
}
结果
index:4
可以看出每次循环之后,再次计算.需要的依然是key,arr,minIndex,maxIndex但是结果在收敛,那么我们可以直接将minIndex,maxIndex这两个参数放入方法中作为参数,由调用者手动初始化,那么我们来改写一下代码:
public static int binarySearch(int key, int[] arr, int minIndex, int maxIndex) {
while (true) {
//当minIndex > maxIndex说明待查找的数不存在
if (minIndex > maxIndex) {
return -1;
}
//每循环一次midIndex都要折半
int midIndex = minIndex + (maxIndex - minIndex) / 2;
//根据条件移动头尾光标,如果正好相等则直接返回
if (key < arr[midIndex]) {
maxIndex = midIndex - 1;
} else if (key > arr[midIndex]) {
minIndex = midIndex + 1;
} else {
return midIndex;
}
}
}
再来看测试代码
public static void main(String[] args) {
int[] arr = {1, 3, 6, 9, 11, 33, 55, 77};
int index = binarySearch(33, arr, 0, arr.length - 1);
System.out.println("index:" + index);
}
结果
index:5
那么既然被调用的方法每一次循环得到的结果再运算的参数跟运算前一样,那么我们就可以考虑是否能使用递归,再来看下递归的特点:
1.递归总有一个最简单的情况---方法的第一条语句总是一个包含return的条件语句.
当minIndex > maxIndex时就是那个最简单的情况,只要满足这个条件.直接return,第一条满足
2.递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况.
每一次计算之后,问题的范围都在缩小,逐渐收敛,这一条满足
3.递归调用的父问题和尝试解决的子问题之间不应该有交集
每一次计算之后,虽然还是使用之前的数组，但是查找后被舍弃的部分已经不参与运算了，可以等同于一个新数组(为了方便理解，你当然可以在每一次计算之后将剩下的部分赋给一个新的子数组)，下一次计算等同于在使用新的数组做计算,不会再跟之前的数组有任何关系,这一条也满足
那我们尝试一下递归写法:
public static int binarySearch(int key, int[] arr, int minIndex, int maxIndex) {
//当minIndex > maxIndex说明待查找的数不存在
if (minIndex > maxIndex) {
return -1;
}
//每循环一次midIndex都要折半
int midIndex = minIndex + (maxIndex - minIndex) / 2;
//根据条件将头尾光标重新赋值并递归,如果正好相等则直接返回
if (key < arr[midIndex]) {
return binarySearch(key, arr, minIndex, midIndex - 1);
} else if (key > arr[midIndex]) {
return binarySearch(key, arr, midIndex + 1, maxIndex);
} else {
return midIndex;
}
}
再将方法重载一次,将参数简化,提供给调用者的时候,只需要输入两个参数,跟最开始的写法一样
public static int binarySearch(int key, int[] arr) {
return BinarySearch(key, arr, 0, arr.length - 1);
}
请看测试代码
public static void main(String[] args) {
int[] arr = {1, 3, 6, 9, 11, 33, 55, 77};
int index = binarySearch(9, arr);
System.out.println("index:" + index);
}
运行结果:
index:3
