算法(4th ed)(32):基础——基础编程模型 3.6.4

阅读数:28 2019 年 10 月 30 日 06:46

算法(4th ed)(32):基础——基础编程模型 3.6.4

(静态方法:递归)

方法可以调用自己(如果你对递归概念感到奇怪,请完成练习 1.1.16 到练习 1.1.22)。例如,下面给出了 BinarySearchrank() 方法的另一种实现。我们会经常使用递归,因为递归代码比相应的非递归代码更加简洁优雅、易懂。下面这种实现中的注释就言简意赅地说明了代码的作用。我们可以用数学归纳法证明这段注释所解释的算法的正确性。我们会在 3.1 节中展开这个话题并为二分查找提供一个这样的证明。

编写递归代码时最重要的有以下三点。

  • 递归总有一个最简单的情况——方法的第一条语句总是一个包含return 的条件语句。
  • 递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况。在下面的代码中,第四个参数和第三个参数的差值一直在缩小。
  • 递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中,两个子问题各自操作的数组部分是不同的。
复制代码
public static int rank(int key, int[] a)
{ return rank(key, a, 0, a.length - 1); }
public static int rank(int key, int[] a, int lo, int hi)
{ // 如果 key 存在于 a[] 中,它的索引不会小于 lo 且不会大于 hi
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}
二分查找的递归实现

违背其中任意一条都可能得到错误的结果或是低效的代码(见练习 1.1.19 和练习 1.1.27),而坚持这些原则能写出清晰、正确且容易评估性能的程序。使用递归的另一个原因是我们可以使用数学模型来估计程序的性能。我们会在 3.2 节的二分查找以及其他几个地方分析这个问题。

评论

发布