学习递归的另一种方法

每个学期，我都会通过一项调查，以获取有关我的教学的一些反馈。上学期终于有人给我写一篇新文章的想法。特别是，他们想了解有关递归的更多信息，所以我认为我会综合一些技巧。

递归概述

对于那些可能是第一次学习递归的人，我想我会提供一些有关概念的概述。

特别地，递归是一种依赖于解决较小子问题的问题解决技术。换句话说，不是继续直接解决问题，而是继续分解问题，直到找到可以实际解决的较小问题为止。然后，我们使用最小子问题的答案来进行倒推，直到获得原始问题的答案为止。

例如，假设我们要计算2 ⁶ 。通常，我们会将其分解为重复乘法。换句话说，我们将2乘以6乘以自身，得出64。在计算机科学中，我们将此称为问题解决技术迭代，通常以循环的形式看到它：

 def iterative_power(base, exponent): product = 1 for i in range(exponent): product *= base return product  print(iterative_power( 2 , 6 ))

当然，如果我们已经知道一些较小的子问题的答案，该怎么办。例如，如果我们知道2 ⁵是32怎么办？然后，我们可以通过将2 ⁵乘以2来直接计算2 ^6。这就是递归的思想：

 def recursive_power(base, exponent): if exponent == 0 : return 1 else : return recursive_power(base, exponent - 1 ) * base

在本文中，我们将介绍递归的另一种思考方式。希望它可以帮助您比以前更好地理解概念。

为什么递归如此困难？

虽然函数式编程目前正在卷土重来，但是它对我们学习编码的方式并没有产生太大的影响。结果，大多数人开始使用类似C的命令式编程语言进行编码。例如，我开始使用Java并转入C，C ++，C＃和Python等语言。

不幸的是，学习像C这样的语言的弊端在于，我们在解决问题的思维方式上受到了一定的限制。换句话说，以这些语言提供给我们的工具集在很大程度上偏向分支（即，如果语句和循环）。

结果，递归背后的直觉并不是从一开始就建立的。取而代之的是，我们被迫使用与迭代解决方案相关的人为示例引入递归。否则，我们还会如何联系。

另外，像C这样的命令性语言在引入递归之前需要大量的开销。例如，在开始考虑递归之前，您可能必须学习变量，分支和函数等概念。实际上，直到我第一次学习数据结构课程时，我才亲自介绍这个概念。

总而言之，可能很难掌握递归，因为它需要您对编码的理解成为现实。幸运的是，有多种方法可以打破这种循环（绝对是双关语）。

通过合同设计学习递归

最近，我在俄亥俄州立大学接受培训以教授软件组件课程，而该课程涵盖的主题之一是递归。当然，那时我已经非常熟悉递归，但是我认为他们教这个主题的方式确实很优雅。结果，我认为我可以将该方法传递给您。也就是说，我们需要首先解决按合同设计。

合同设计概论

如果我在过去写过一些有关“按合同设计”的文章（主要是指JUnit测试），请再说一遍，对此我深表歉意。自然地，我认为我现在是一个稍微好一点的作家，但也可以随时参考该文章。

无论如何， 按合同设计 （DbC）是一种编程哲学，在该哲学中，我们根据合同来考虑功能。换句话说，当用户使用我们的功能之一时，我们希望为他们提供某种保证。特别是，我们要求用户在一定条件下（又称为前提条件）执行每个功能。因此，我们保证每个函数都会以某种特定的方式运行（aka后置条件）。

DbC在递归中很重要，因为它允许我们精确地指定函数在特定条件下将执行的操作。例如，只要我们指定一些先决条件，我们先前定义的幂函数将起作用：

两个参数都必须是整数（可以通过一些类型提示来解决）
power参数不能为负

其结果是，我们的承诺，这两个函数将返回base提出了一些power 。如果用户输入了无效的输入，我们将不会做出任何承诺，因为他们显然违反了合同。当然，我们总是可以提供某种输入验证来防止令人讨厌的错误，但这超出了DbC的范围。

所有人免费午餐

在OSU中，我们通过完全忽略递归的思想来介绍递归。取而代之的是，我们利用对合同设计的了解，开始隐式地实现递归函数。

例如，让我们再看看我们一直在谈论的这个幂函数：

 def power(base: int , exponent: int ) -> int : "" "Computes the base ^ exponent. Precondition: exponent >= 0 Postcondition: base ^ exponent "" " return FreeLunch.power(base, exponent)

在此示例中，我们从名为FreeLunch的神奇库中引入了新的幂函数。就我们而言，这一新的幂函数与我们编写的函数完全相同，即相同的合同。

现在，为了论证，让我们说这个FreeLunch功效函数有一个要求：其输入必须比功效函数的输入“小”。我们怎么做才能确保这项工作有效？

好吧，如果我们减小指数，我们可以通过乘以底数（即x ⁵ = x ⁴ * x）将其加回去。让我们尝试一下：

 def power(base: int , exponent: int ) -> int : "" "Computes the base ^ exponent. Precondition: exponent >= 0 Postcondition: base ^ exponent "" " return FreeLunch.power(base, exponent - 1 ) * base

在这一点上，我们如何去验证它是否有效？好吧，让我们尝试一些输入。例如，我们可以再次尝试2 ⁶ 。如果我们遍历代码，就会注意到我们调用了FreeLunch.power(2, 5) ，这是一个完全有效的输入。换句话说，我们将得到32，然后乘以2得到64，这是正确的答案。

也就是说，是否有任何输入会失败？绝对！由于FreeLunch功效函数与我们的FreeLunch函数具有相同的合同，因此存在无效的输入。例如，我们应该避免FreeLunch幂函数的值小于0的任何情况：

 def power(base: int , exponent: int ) -> int : "" "Computes the base ^ exponent. Precondition: exponent >= 0 Postcondition: base ^ exponent "" " if exponent == 0 : return 1 else : return FreeLunch.power(base, exponent - 1 ) * base

现在，可以确定我们的幂函数可以工作了。

天下没有免费的午餐

您可能会想到，以这种复杂的方式实现幂函数只是一种欺骗您使用递归的练习。换句话说，我们可以完全删除上面的FreeLunch类，并且我们将拥有一个功能齐全的递归解决方案：

 def power(base: int , exponent: int ) -> int : "" "Computes the base ^ exponent. Precondition: exponent >= 0 Postcondition: base ^ exponent "" " if exponent == 0 : return 1 else : return power(base, exponent - 1 ) * base

现在的问题是：为什么我们要经历所有这些努力来引入递归？毕竟，几乎所有其他递归教程都利用某种堆栈。我们为什么不这样做呢？

虽然使用堆栈教递归完全有效，但对学生来说通常很麻烦。例如，想象一下在不使用我们的FreeLunch技巧的情况下通过上面的幂函数进行跟踪。如果我们提供两个随机输入（例如2的底数和6的指数），则必须跟踪每个幂函数调用，直到达到最小的子问题为止。在纸面上，这是一个简单示例的六种痕迹！

通过这种方式进行授课时，学生在尝试各种程序输入时经常会发现自己迷失在递归中。如果他们转而放弃对合同的怀疑和信任，他们可以一次证明自己的功能有效。当然，他们需要特别注意其输入（请参阅数学归纳法）。