recursion - 使用递归时如何 "leap of faith"？

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 );
  }

不需要信仰的飞跃；我知道递归调用会起作用，因为我编写了方法来做到这一点。