Java递归函数与算法讲解系列二

在上一篇文章中讲了递归函数的基本原理和示例，本篇继续结合具体案例讲解递归在现实中的应用。

用递归轨迹说明标尺绘图

递归drawInterval方法的执行可以使用递归跟踪可视化。然而，drawInterval的跟踪要比factorial示例复杂得多，因为每个实例都进行两次递归调用。为了说明这一点，我们将以一种类似于文档大纲的形式显示递归跟踪。见图：

调用drawInterval（3）的部分递归跟踪。drawInterval（2）的第二种调用模式没有显示，但它与第一种模式相同。

二进制搜索

在本节中，我们将描述一个经典的递归算法，二进制搜索，用于在存储在数组中的n个元素的排序序列中有效地定位目标值。这是最重要的计算机算法之一，这也是我们经常按排序顺序存储数据的原因

数组中按排序顺序存储的值。最上面的数字是指数。

当序列未排序时，搜索目标值的标准方法是使用循环检查每个元素，直到找到目标或耗尽数据集为止。这种算法被称为线性搜索或顺序搜索，它在O（n）时间（即线性时间）内运行，因为每个元素都是在最坏的情况下检查的。

当序列是排序的和可索引的，有一个更有效的算法。（凭直觉，想想你如何用手完成这项任务！）如果我们考虑序列中任意一个元素的值为v，那么我们可以确定序列中该元素之前的所有元素的值都小于或等于v，并且序列中该元素之后的所有元素的值都大于或等于v。这个观察使我们能够使用一个变量快速“定位”搜索目标在儿童游戏“高低”中，如果在当前的搜索阶段，我们不能排除这个项目与目标匹配，我们就称序列中的一个元素为候选元素。该算法保持低和高两个参数，使所有候选元素的索引至少为低，最多为高。最初，低=0，高=n−1。然后我们将目标值与中间候选值进行比较，即，具有索引的元素：

mid = ⌊(low + high)/2⌋

我们考虑三种情况：

• 如果目标等于中间候选项，则我们找到了我们正在寻找的项目，搜索成功结束。
• 如果目标小于中间候选值，则我们在序列的前半部分重新出现，即从低到中-1的指数间隔。
• 如果目标大于中间候选值，则我们在序列的下半部分重复，即指数从mid+1到high的间隔。

如果低>高，则搜索失败，因为间隔[low，high]为空。

这种算法被称为二进制搜索。我们在代码片段中给出了一个Java实现，并在图中演示了算法的执行。顺序搜索在O（n）时间内运行，而更有效的二进制搜索在O（logn）时间内运行。这是一个显著的改进，如果n是10亿，logn只有30。

/∗∗
 ∗ Returns true if the target value is found in the indicated portion of the data array.
 ∗ This search only considers the array portion from data[low] to data[high] inclusive.
 ∗/
 public static boolean binarySearch(int[ ] data, int target, int low, int high) {
	 if (low > high)
	 	return false; // interval empty; no match
	 else {
		 int mid = (low + high) / 2;
		 if (target == data[mid])
		 return true; // found a match
	 else if (target < data[mid])
	 	return binarySearch(data, target, low, mid − 1); // recur left of the middle
	 else
	 	return binarySearch(data, target, mid + 1, high); // recur right of the middle
	 }
 }

排序数组上二进制搜索算法的一种实现。

在包含16个元素的已排序数组上对目标值22进行二进制搜索的示例。

文件系统

现代操作系统以递归的方式定义文件系统目录（也称为“文件夹”）。也就是说，一个文件系统由一个顶级目录组成，这个目录的内容由文件和其他目录组成，这些目录又可以包含文件和其他目录，等等。操作系统允许对目录进行任意深度的嵌套（只要有足够的内存），尽管必须有一些只包含文件的基目录，而不包含其他子目录。下图给出了这种文件系统的一部分的表示。

考虑到文件系统表示的递归性质，操作系统的许多常见行为（如复制目录或删除目录）都是用递归算法实现的，这一点也不奇怪。在本节中，我们考虑这样一种算法：计算嵌套在特定目录中的所有文件和目录的总磁盘使用量。

为了便于说明，下图描绘了示例文件系统中所有条目所使用的磁盘空间。我们区分每个条目使用的即时磁盘空间和该条目和所有嵌套功能部件使用的累积磁盘空间。例如，cs016目录只使用2K的立即空间，但总共使用249K的累积空间。

图中给出的文件系统的同一部分，但带有额外的注释来描述所使用的磁盘空间量。在每个文件或目录的图标中是该工件直接使用的空间量。每个目录的图标上方都指示了该目录及其所有（递归）内容所使用的累积磁盘空间。

一个条目的累积磁盘空间可以用一个简单的递归算法来计算。它等于条目使用的即时磁盘空间加上直接存储在条目中的任何条目的累计磁盘空间使用量之和。例如，cs016的累计磁盘空间是249K，因为它本身使用2K，等级累积使用8K，家庭作业中累积使用10K，程序中累积使用229K。

该算法的伪代码在代码片段如下：

Algorithm DiskUsage( path):
	Input: A string designating a path to a file-system entry
	Output: The cumulative disk space used by that entry and any nested entries
	total = size( path) {immediate disk space used by the entry} 
	if path represents a directory then
		for each child entry stored within directory path do
			total = total + DiskUsage( child) {recursive call}
	return total

一种计算嵌套在文件系统项上的累积磁盘空间使用量的算法。我们假设method size返回一个条目的即时磁盘空间。

java.io.File Class

为了在Java中实现计算磁盘使用量的递归算法，我们依赖于java.io.File文件班级。此类的实例表示操作系统中的抽象路径名，并允许查询该操作系统项的属性。我们将采用以下方法：

• new File（pathString）或new File（parentFile，childString）通过提供一个新的目录项，或者提供一个新的目录项来指定一个新的目录项，或者在这个目录中提供一个新的目录项。
• file.length()返回由文件实例（例如，/user/rt/courses）表示的操作系统项的即时磁盘使用量（以字节为单位）。
• file.isDirectory()如果文件实例表示目录，则返回true；否则返回false。
• file.list()返回一个字符串数组，指定给定目录中所有项的名称。在我们的示例文件系统中，如果我们对与path/user/rt/courses/cs016关联的文件调用此方法，它将返回一个包含以下内容的数组：{“grades”、“homeworks”、“programs”}。

Java实现

通过使用File类，我们现在将算法从下面的代码片段实现。

/∗∗
∗ Calculates the total disk usage (in bytes) of the portion of the file system rooted
∗ at the given path, while printing a summary akin to the standard 'du' Unix tool.
∗/
public static long diskUsage(File root) {
	long total = root.length( ); // start with direct disk usage
	if (root.isDirectory( )) { // and if this is a directory,
		for (String childname : root.list( )) { // then for each child
			File child = new File(root, childname); // compose full path to child
			total += diskUsage(child); // add child’s usage to total
		}
	}
	System.out.println(total + "\t" + root); // descriptive output
	return total; // return the grand total
}

磁盘文件递归报告系统的使用方法。

以下是递归视频讲解：