12.10　递归版本

也可以用递归方法实现二分法查找。为此可编写一个将 low 和 high 作为参数的方法，并将第 3 步和第 4 步转换为递归调用。代码类似于下面这样：

  1. public static int binarySearch(Card[] cards, Card target,
  2.                                int low, int high) {
  3.     if (high < low) {
  4.         return -1;
  5.     }
  6.     int mid = (low + high) / 2;                               // 第1步
  7.     int comp = cards[mid].compareTo(target);
  9.     if (comp == 0) {                                          // 第2步
  10.         return mid;
  11.     } else if (comp < 0) {                                    // 第3步
  12.         return binarySearch(cards, target, mid + 1, high);
  13.     } else {                                                  // 第4步
  14.         return binarySearch(cards, target, low, mid - 1);
  15.     }
  16. }

这里没有用 while 循环，而是用了一条 if 语句来终止递归。如果 high 小于 low，它们之间就不可能有 Card 对象，因此指定的 Card 对象肯定不在数组中。

编写递归程序时的两种常见错误是：忘记包含基线条件；编写的递归调用导致基线条件根本不可能满足。这两种错误都会导致无限递归，进而引发 StackOverflowException 异常。