关于递归的几点思考

现在我们到了启蒙的第三个层次：递归。在我看来，在没有研究支持的情况下胡乱猜测，递归与数学归纳和矛盾证明有着相似的概念挑战。也许与数学归纳法的相似之处是相当明显的，也许因矛盾而产生的相似之处就不那么明显了，但是暂时不要忘记我的意思。这里可能值得注意的是，一些(大多数？)。早期的编程语言(特别是Fortran77)不允许函数自称为--递归调用是被明确禁止的。

在递归中我们定义了一个函数，但在计算要返回的值时，允许该函数调用自己。对于一些人来说，这简直是无法理解，或者是胡说八道，因为一个还没有定义的函数怎么能以某种方式使用自己来计算自己呢？数学归纳法也出现了类似的问题。这里我们想证明一个命题，但不知何故，我们可以神奇地用命题的真实性来证明这个命题，这似乎是明显的无稽之谈。我们怎么才能理解它呢？因此，让我们举一个具体的例子，解决河内的双子塔问题。我们有三个位置，A、B和C，以及不同大小的磁盘集合。目前它们都在位置A堆叠，我们希望它们在位置B。但这是有规则的。首先，我们一次只能移动一个磁盘。其次，我们可能永远不会把较大的磁盘放在较小的磁盘上。随机使用其中的一个片刻可以看出，显然有一些方法可以做到这一点，解决方案也有一些结构，但如果有一个严格的解决方案就好了。还有……。是这样的。如果只有一张磁盘，则将其移动到您想要的位置。完成。如果有多个磁盘，请将其视为最底层的磁盘L，其余部分为R。我们要将L+R从位置A移至位置B，因此我们将R移至C，然后将L移至B(我们所需的最终位置)，最后将R移至位置B中L的顶部。但是请稍等，R可能有很多磁盘，而您还没有告诉我如何移动它们！您可以使用相同的指令将R从它所在的位置移动到我想要的位置。

……。诸若此类。基本的想法是这样的。从展示如何解决最简单的可能情况开始。有了这个问题，我们已经展示了当只有一个磁盘时如何解决这个问题。现在考虑任何一个案例，并假设(这是有些人觉得棘手的一点)我们可以解决所有在某种意义上比较简单的案例。如果我们能展示如何将我们正在尝试解决的案例分解成几个更简单的案例的组合，那么我们就完成了。(这是一些人觉得很棘手的一点)，我们可以解决所有在某种意义上比较简单的案例。如果我们能展示如何将我们正在努力解决的案例分解成几个更简单的案例的组合，那么我们就完成了。这就是我们上面所做的。我们遇到了N个磁盘，我们假设我们可以在少于N个的情况下解决塔问题。然后我们观察到，如果我们移走N-1个磁盘(假设我们可以)，移动最后一个磁盘，然后再次移动N-1个磁盘(同样，我们可以)，那么我们就完成了。因此，要实现这一点，我们需要一些东西：所以这里有一些简单的示例。在每种情况下，您都会看到代码选择了最明显的最简单的情况。然后，在处理完这些问题之后，我们使用一个更简单的案例来计算所需的值。Def阶乘(N)：#如果n<；0：return'；error！'；if n==0：return 1返回n*阶乘(n-1)，我们假设n是整数。

阶乘是一个经典的递归例子，通常写成n！，n的阶乘是从1到n(含1到n)的所有整数的乘积，其中0！定义为1(出于我们不会在此介绍的原因)。所以我们在这里计算n！如果n是零，那么答案是1，否则我们计算(n-1)！并乘以n。事实上，在现实生活中你永远不会像这样计算阶乘，但它是这个过程如何工作的一个合理的例子。Def Fibonacci(N)：#假设n是整数，如果n<；0：返回'；错误！'；如果n==0：如果n==0：返回1如果n==1：返回1返回Fibonacci(n-2)+Fibonacci(n-1)。

该代码遵循斐波那契数的通常定义，其中F(0)=F(1)=1，然后每个斐波那契数是前面两个数字的和。实际上，这样做的问题是要花费指数级的时间来计算！使用此例程计算Fib(30)需要超过一百万次调用。有一些更快、更实用的方法，但是这个例程是用来演示递归的。如果你想计算斐波纳契数，不要这样做。真的。Don'；T.def BINARY_SEARCH(K，V，L，U)：#K是一个可以找到的东西#V-排序后的列表#L，U-非负整数#我们假设如果K在V中，#并且在位置I，则#L<；=I<；U如果不是L<；U：return'；not find'；if L+1=U：if V[L]==K：return L：return'；not find'；(如果不是L<；U：返回'；未找到'；如果L+1=U：如果V[L]==K：返回L：返回'；未找到'；M=Floor((L+U)/2)if K<；V[m]：返回BINARY_SEARCH(K，V，L，m)否则：返回BINARY_SEARCH(K，V，m，U)。

这是一个比较复杂但相当现实的例子。我们正在对一种特殊的物品--

假设有一些我们的命题不成立的n，并考虑最小的n，我们就会得出一个矛盾。我们的第一个失败不可能是n=1，因为作为归纳法证明的一部分，我们已经证明了我们的命题在这种情况下是正确的，所以这意味着n>；1。现在考虑n-1。因为n是第一个失败，所以命题对于n-1是正确的。因为我们有一个归纳法证明，所以我们有一个证明，如果它对n-1是真的，那么它对n也是真的。所以它对n也是真的。所以假设它在某个地方失败会导致一个矛盾。因此，我们用矛盾证明来证明，归纳法证明的步骤足以表明某事是真的。嗯，不完全是。我们也用过这个最小的失败案例，所以它使用了良好的秩序原则，所以它还在继续。只要说这些事情都是有联系的，有些事情对一些人来说更明显，而另一些事情对其他人来说更明显就够了。简而言之，这可能很复杂，当你第一次遇到这些想法时，它们可能会有点令人望而生畏，而不是不知所措。对于某些人(也许几乎所有人！)。只有随着时间的推移，它们才会变得容易和明显。所以我们有了编程的第四个层次，那就是对并行编程的真正理解。我们将把那件事留到另一个时间再谈。你可以在这里给我们发个信息。它不会发布，它只会给我们发送一封电子邮件，而且它是一种简单的方式来询问任何问题或发表任何评论，而不必单独发送电子邮件。所以只要填好空格，然后