使用递归时如何“信仰之跃”？

Question

对于我来说，在制作递归方法时。我总是需要花费很多时间来做这件事，因为我会做一些测试用例，看看我的递归用例是否有效并绘制堆栈图。然而，当我问其他人时，他们只是说我需要相信自己它会起作用。如果您不知道递归情况下发生了什么，我该如何相信？

Answer 1

您可以定义递归情况下发生的情况，就像定义方法的其余部分一样。想象一下，其他人编写了一种方法来执行您正在编写的方法；你这样称呼不会有问题，不是吗？唯一的区别是您是该方法的作者，而它恰好是正在编写的方法。

例如：我正在编写以下方法：

// Sort array a[i..j-1] in ascending order
method sort_array( a, i, j ) {
  ..
}

基本情况很简单：

  if ( i >= j-1 ) // there is at most one element to be sorted
    return;       // a[i..j-1] is already sorted

现在，如果事实并非如此，我可以执行以下操作：

  else {
    k = index_of_max( a, i, j );
    swap( a, j-1, k );

此时，我知道它a[j-1]具有正确的值，因此我只需要对它之前的内容进行排序 - 幸运的是，我有一个方法可以做到这一点：

    sort_array( a, i, j-1 );
  }

不需要任何信念的飞跃；我知道递归调用会起作用，因为我编写了执行此操作的方法。