递归之一

Posted on | In | 阅读数

编写递归最重要的三点之一

  1. 递归总有一个最简单的情况。
    • 方法的第一条语句总是包含return的条件语句
  2. 递归调用总是尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。


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

二分查找。（用好重载是真的牛）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//这个肯定是对外提供的api，下面重载的方法才是具体实现，真牛
public static int binarySearch(int[] orderArray, int targetValue) {
       return binarySearch(orderArray, targetValue, 0, orderArray.length - 1);
   }

public static int binarySearch(int[] orderArray, int targetValue, int minIndex, int maxIndex) {
       if(orderArray==null || orderArray.length == 0) return Integer.MIN_VALUE;

       int index = (minIndex + maxIndex)/2;

       if( targetValue > orderArray[index] ) return binarySearch(orderArray, targetValue, index, maxIndex);
       if( targetValue < orderArray[index] ) return binarySearch(orderArray, targetValue, minIndex, index);
       
       return index;
   }