5.9　递归栈图

第 4 章用栈图来表示程序在方法调用期间的状态，使用相同的图可让递归方法更容易解释。

前面说过，每当方法被调用时，Java 都会创建一个新的栈帧，其中包含该方法的形参和变量。图 5-1 是使用 3 调用 countdown 时的栈图。

图 5-1：程序 countdown 的栈图

根据约定，main 的栈帧位于最上面，而栈是向下延伸的。main 的栈帧是空的，因为它不包含任何变量。（它包含形参 args，但由于没用这个形参，因此没有在栈图中列出。）

countdown 有四个栈帧，分别与形参 n 的不同值对应。在最后一个栈帧中 n=0 被称为基线条件（base case）。因为它没有执行递归调用，所以下面没有其他的栈帧。

如果递归方法不包含基线条件，或永远不能满足基线条件，那么栈将没完没了地增大，至少从理论上说如此。实际上，栈的长度是受限制的，超过限制将引发 StackOverflowError 异常。

例如，下面的递归方法就不包含基线条件：

public static void forever(String s) {
    System.out.println(s);
    forever(s);
}

这个方法将不断地显示指定的字符串，直到栈溢出，进而引发异常。