深入探索

简单递归

如果你之前从未使用过递归（recursion），则本章中的递归“目录遍历”（directory-walking）方法可能需要一些说明。为了阐明递归是如何工作的，让我们看一个更简单的例子。加载 recursion.rb 程序：

$outercount = 0
def addup( aNum )
  aNum += 1
  $outercount +=1
  puts( "aNum is #{aNum}, $outercount is #{$outercount}" )
  if $outercount < 3 then
    addup( aNum ) #<= recursive call to addup method
  end
  puts( "At END: aNum is #{aNum}, outercount is #{$outercount}" )
end
addup( 0 ) #<= This is where it all begins

这包含递归方法 addup，其唯一的目的是从 1 到 3 计数。addup 方法接收一个整数值作为传入参数 aNum。

addup( aNum )

还有全局变量 $outercount，它存在于 addup 方法之外。每当 addup 方法执行时，1 将添加到 aNum，1 也会添加到 $outercount。然后，只要 $outercount 小于 3，addup 方法中的代码就会再次调用相同的方法（addup），并将 aNum 的新值传递给它：

if $outercount < 3 then
  addup( aNum )
end

让我们来看看会发生什么。通过值 0 来调用 addup 以启动整个过程：

addup( 0 )

addup 方法将 aNum 和 $outercount 都加 1，因此两个变量现在都具有值 1。测试 test($outercount < 3) 的计算结果为 true，因此 aNum 作为参数传递给 addup。再次向两个变量添加 1，因此 aNum 现在为 2，$outercount 也为 2。现在 aNum 再次传递给 addup。然后再将 1 添加到两个变量中，给出每个值 3。然而，这次测试条件失败，因为 $outercount 不再小于 3。因此调用 addup 的代码被跳过，我们到达方法的最后一行：

puts( "At END: aNum is #{aNum}, outercount is #{$outercount}" )

这会打印出 aNum 和 $outercount 的值，正如我们所料，它们都是 3。

现在已经到达此方法的末尾，“控制流”会在最初调用该方法的代码之后立即返回到代码行。这里，调用 addup 方法的代码行恰好位于方法本身内部。这里是：

addup( aNum )

此后的第一个可执行代码行是（再次）方法的最后一行，它打印出两个变量的值：

puts( "At END: aNum is #{aNum}, outercount is #{$outercount}" )

所以我们回到了之前的“执行点” - 我们递归调用 addup 方法的点。那时，aNum 的值是 2，也是它现在的值。如果这看起来令人困惑，那就试着想想如果 aNum 已经是 2 ，然后我们调用其它一些不相关的方法，那么会发生什么。从该方法返回时，aNum 当然仍然具有值 2。这就是发生在这里的一切。唯一的区别是这种方法恰好调用自己而不是其它方法。

该方法再一次退出，控制再次返回到调用该方法的代码之后的下一个可执行代码行 - 并且 aNum 的值又回到了自己的历史记录中 - 它现在具有值 1。但是，$outercount 变量存在于方法之外，不受递归的影响，因此它仍然是 3。

如果你可以访问可视化调试器，那么如果在第 9 行放置一个断点（if $outercount < 3 then），将 aNum 和 $outercount 添加到 Watch 窗口，并在你命中断点之后重复进入代码，整个过程将变得更加清晰。

此屏幕截图显示了在 Ruby In Steel 中调试的递归程序。我可以单步执行源代码，使用调用堆栈来跟踪当前递归的“级别”（调用 addup 方法的次数），并使用Watch 窗口监视变量的当前值。