5.6　递归

“递归调用方法”或者“用递归实现方法”意味着方法调用它自身。有时这是实现算法最简单的方式。代码清单5.18统计目录及其子目录中的所有C#源代码文件（*.cs）的代码行数。

代码清单5.18　返回目录中所有.cs文件的代码行数

注①：该代码可用using语句改进，但因为我们还没有讲到，所以暂时不使用。

输出5.9展示了代码清单5.18的结果。

输出5.9

程序首先将第一个命令行参数传给DirectoryCountLines()，或直接使用当前目录（如果没有提供参数）。方法首先迭代当前目录中的所有文件，累加每个.cs文件包含的源代码行数。处理好当前目录之后，将subdirectory传给Directory.CountLines()方法以处理每个子目录。同样的过程针对每个子目录反复进行，直到再也没有更多子目录可供处理。

不熟悉递归的读者刚开始可能觉得非常烦琐。但事实上，递归通常都是最简单的编码模式，尤其是在和文件系统这样的层次化数据打交道的时候。不过，虽然可读性不错，但一般不是最快的实现。如果必须关注性能，开发者应该为递归实现寻求一种替代方案。至于具体如何选择，通常取决于如何在可读性与性能之间取得平衡。

初学者主题：无限递归错误

用递归实现方法时，常见错误是在程序执行期间发生栈溢出（stack overflow）。这通常是由无限递归造成的。假如方法持续地调用自身，永远抵达不了标志递归结束的位置，就会发生无限递归。必须仔细检查每个使用了递归的方法，验证递归调用是有限而非无限的。

下面以伪代码的形式展示了一个常用的递归模式：

M(x)
{
  if x已达最小，不可继续分解[1]
    返回结果
  else
    (1) 采取一些操作使问题变得更小
    (2) 递归调用M来解决更小的问题
    (3) 根据(1)和(2)计算结果
    返回结果
}

不遵守这个模式就可能出错。例如，如果不能将问题变得更小，或者不能处理所有可能的“最小”情况，就会递归个不停。

[1] 或者说“if满足递归结束条件（base case）”。——译者注