2.2.2 箱式跟踪
可以使用箱式跟踪帮助理解递归并调试递归函数。不过，这种机械性策略不能替代对递归的直观理解。箱式跟踪演示编译器如何频繁地实现递归。通过读取下面对该技术的描述可知，各个箱大致对应于一个活动记录，编译器一般在函数调用实现中使用这个活动记录。C++片段2中将进一步讨论活动记录。
注释：活动记录是为函数调用创建的
下面通过递归函数fact讲述箱式跟踪，这个函数返回一个值。
(1) 标记递归函数体中的各个递归调用。一个函数中可能有几个递归调用，所以有必要加以区别。这些标记有助于跟踪在函数调用完成后必须返回的正确位置。例如，用字母A标记函数体内的fact(n-1)表达式。
- if (n == 0)
- return 1;
- else
- return n * fact(n-1);
- ○A
每次递归调用后，都会返回点A。用返回值替换fact(n-1)，并继续计算表达式n*fact(n-1)。
注释：标记函数内的每次递归调用
(2) 在执行过程中，用一个新箱表示各个函数调用；新箱指示函数的局部环境。具体地讲，每个箱包含：
形参列表中的参数值。
函数的局部变量。
从当前箱的各个递归调用所返回的值的占位符。标记这个占位符，以与第1步中的标记相对应。
函数本身的值。
注释：每次函数被调用的时候，都会用新箱表示局部环境
当第一次创建箱时，只知道输入参数的值，其他值则要根据函数的执行来判断。例如，可以为fact(3)的调用创建如图2-3所示的箱(后面的示例将看到，引用参数的处理方式同值参数和局部变量的处理方式略有不同)。
(3) 绘制一个箭头，从启动递归过程的语句指向第一个箱。接下来，在递归调用后新建一个箱(如第2步所述)，绘制一个箭头，从执行调用的箱指向新箱。标记各个箭头，以与递归调用的标记(见第1步)对应；这个标记指示调用完成后准确的返回位置。例如，图2-4显示cout<<fact(3)语句中对fact的调用生成的前两个箱。
(4) 在通过前两步新建箱并绘制箭头后，开始执行函数体。不管当前箱是如何生成的，对函数局部环境中值的引用都对应当前箱中的值。
(5) 在退出函数时，取消当前箱，并沿箭头返回调用该函数的箱。于是，这个箱成为当前箱，箭头上的标记指明了下面将在那个位置执行函数。用刚终止的函数调用所返回的值替换当前箱的对应的占位符。
图2-5显示了调用fact(3)的完整箱式跟踪。在这些顺序图中，当前箱在箭头路径的最深处，并用浅灰色显示；被取消的箱用虚框表示，颜色为深灰色。
提示：箱式跟踪与合适的cout语句配合，可以有效地辅助调试递归函数。这种语句应该报告程序中递归调用发生的位置，以及进入或者退出函数处的输入参数和局部变量的值。在函数的最终版本中一定要记得删除这些语句。
问题2 编写问题1给定函数的箱式跟踪。
