如何不教递归

我们都知道如何教授递归。我们已经做到了数十年。我们选择了一些久经考验的示例-斐波那契数和阶乘为领先的候选人-并用它们来教授总体思想。它们是如此经典，直接来自神灵：您可以在书中找到尼古拉斯·沃思（Niklaus Wirth）这样的人。

但我在这里告诉您他们弄错了，从那以后每个人都在弄错。学生们不知所措，困惑不解，继续成为重复此过程的下一代教师。但是，我们不需要重复此循环。我们有更好的方法。

首先，我们来看一下规范示例中的问题。

首先，几乎没有人需要计算阶乘。我已经进行了大约35年的编程，而我唯一需要计算阶乘的时间是在做休闲数学或使用编程来探究一些特别棘手的组合问题时。否则，我永远不需要阶乘。

其次，答案没有意义。很快，13的阶乘是多少？大多数人不知道，并且（与上述情况有关）不在乎。答案无法辨认。大多数程序员认可3628800的唯一原因是因为我们已经在“足够大的数字”上测试了阶乘以确认其有效，而不是因为我们实际上对此很在意。如果您采用要求学生在编写代码之前先开发示例的课程，则学生很难独立地编写答案。许多人会首先实施它并插入答案。

第三，阶乘在大多数语言中具有较差的数值属性。除非您具有对大数的内置自动支持，否则您很快就会获得以奇怪的科学计数形式显示的答案，或者更糟的是会出现溢出（在许多语言中，使用默认整数，阶乘17是-288522240）。

最后，许多学生甚至使用循环编写了类似阶乘的程序，甚至连阶乘本身也是如此。他们（应该！）向教师问的一个自然问题是：“为什么我要再次这样做？”答案不可避免地是：“因为我要你这样做。”没有更好的方法来关闭学生。

因此，让我们总结一下“递归体验”：一个无用的问题，无法识别的答案，行为古怪，使用不必要的新技术，而您不得不使用“因为”。

首先，几乎没有人需要计算斐波那契数。我已经进行了大约35年的编程，而我唯一需要的时间就是进行recrea时，您会知道它的发展方向。不过，我确实发现它们在转换英里和公里之间很有用。

其次，答案没有意义，并且学生将再次很难独立编写答案（什么，要跟踪所有这些呼叫？！？）。第三，它的数字特性很差：大约44，斐波那契是正确的，然后变成负数（这显然是不正确的），然后立即又是一个看起来非常合理的正数，而恰好是完全错误的。我们几十年来一直不在意的主要原因是，因为斐波纳契数在总体上用处不大。

因此，让我们来总结一下“递归体验”：一个毫无用处的问题，无法识别的答案，看上去很古怪的行为，确实运行得很慢（更糟的是，缓慢性首先悄悄地蔓延到您身上，然后突然对您的后背进行锤击）头）。实际上，它的主要价值是一个您不应递归编写的函数。

好吧，我会答应的，很多学生至少听说过最伟大的除数。他们可能会隐约记得在学校中使用它来处理违规情况。因此它很熟悉。

不幸的是，它在不再有意义的情况下很有用。一旦有了编程语言，便有了计算器。除非您要实现计算器（也许甚至在那时），否则您就不需要实现Euclid的算法。

即使这样做，也要承认：您不记得为什么Euclid的算法有效。我当然必须重新推论为什么每次实施该解决方案（每隔几年就出于说明目的）都会产生正确的答案。否则，这只是一个神秘的模式。

那么我们从Euclid算法中得到的教训是什么？那个递归是为不再有用的功能预编码了神秘的模式吗？实际上，除了怪异的数学函数以外，递归对其他有用吗？

首先，我们将从一些发明的东方神秘主义开始。东方主义永远是一种很好的教学手段，对吗？

接下来，这是一个充满代表性问题的问题：您如何精确地代表塔楼的内容？对于初学者来说，这实际上是一个有趣的问题，但是（a）在您进行过编程实践之前并不明显，并且（b）与递归完全无关。因此，您的示例中间存在一个困难的，无关的子问题，它“证明”了递归。难道这完全违反了一次只改变一件事，使学生可以专注于哪些显着性的教学原则吗？ （并且不要忘记，这是指数时间行为的另一个问题！）

此外，如果您不告诉学生（递归）解决方案并让他们自己解决问题，那么您就没有给他们带来编程上的问题：您给了他们一个难题。那是不同的东西。尤其是，河内之塔是一种特别困难的递归-哦，您不知道会有不同的递归吗？继续阅读。

最后，再次有人在乎吗？学生是否相信他们会被召唤帮助僧侣移动磁盘？还有什么其他问题与此类似？如果有的话，我们应该教他们吗，或者我们要以宏伟的隔离呈现这些宏伟的隔离僧侣？

更糟糕的是，这些问题中有许多根本上是静态问题：只有那么多有趣的输入，并且每个输入都有一个完全确定性的解决方案，因此，一旦为标准输入建立了输出表，就可以从根本上解决问题。对于此类问题，明智的做法（尤其是当输入中的运行时复杂度呈指数级时）仅存储答案，而不必再次运行代码。是的，我知道。

另一个久经考验的标准教学方法是愚蠢的笑话：“要理解递归，您必须理解递归”，依此类推。

如果您不了解其中的区别，请不要使用愚蠢的笑话。

如果您确实了解其中的区别，那就不要使用愚蠢的笑话。他们仍然是愚蠢的笑话。

尝试更好的答案可能是问题是“固有的”递归的。但是，这只是观点的局限。关于阶乘的迭代本来就是递归的。上面的所有问题都可以用数学上的说明来更明确地表达，从而消除任何实现指令（例如：最大公约数是最大公约数）：问题的定义与如何查找和搜索无关。找出所有最常见且除数最大的除数的有效解决方案）。

但我知道，我不能就此止步。因此，我将简要介绍如何进行。

在“如何设计程序”（）中，我们对递归有不同的看法。关键思想是这样。

递归来自哪里？认为这源于数据的自我参照。也就是说，递归数据建议使用递归解决方案。这是您了解递归所需的关键见解。一旦您考虑了它，它不仅有意义，而且还证明了为什么大多数其他递归教学方法本质上是不正确的。

讲授设计“配方”。在其中，您可以描述程序（或函数）的数据结构，并在这些数据中标识自我引用。自我指称数据非常简单：甚至孩子也可以理解它们。例如，即使是一个了解生物学的孩子，也可以回答以下基本问题：

他们可以看到结果。他们非常直观地掌握了（生物）家谱的想法。他们甚至可以在编程之前就在很小的时候就看到其他类型的自我参照数据。

接下来，说明数据的结构如何暗示解决方案的结构。此解决方案结构是通用的，称为“模板”。您甚至完全没有想过要解决的确切问题，就从数据结构中完全机械地做到了这一点。

（模板不是一个规则，它是一个建议。它通过提供建议的概述来帮助您克服“空白页”问题。有时，模板会导致正确但效率不高的解决方案。测试更有效提案的参考解决方案。）

另外，您写下问题的示例。在此过程中，您将探索解决方案中的自引用（称为“递归”）如何帮助您解决任务。 （“编程和编程语言”对此进行了更详细的探讨。）

这就是递归函数的来源。这种递归形式称为结构递归，因为递归形式遵循基准的结构。

使用递归数据的其他优点之一是，给定的数据类型通常会产生许多问题。这具有建立比较和对比的优点。学生努力熟悉数据类型并编写好的示例可以在多种设置中获得回报。

学生也可以针对相同的问题空间使用不同的数据类型（如下所述）。这使他们可以考虑每种表示形式相对于其他表示形式的利弊。这是一个与递归无关的通用价值问题，尚未得到足够的研究，但它也特别适合于递归设置。

后来，HtDP教授生成递归，而递归则没有。生成递归需要一个“ ha！”，因为您必须提出非结构性解决方案。为什么使用“生成式”一词？阅读本书，例如考虑以单例头递归定义的列表，列表的其余部分作为尾部。对于这样的列表，有一个自然的排序算法：结构上遵循的一种。

我说这是“自然的”，因为它是您用最少的工作就能得到的，并且最能反映出基准的结构。其他标准分类解决方案需要一些生成步骤。

但是，结构自然会因结构而异。想象一下，您将通过附加两个子列表来表示列表。

原则上，自然数也是递归数据：数字要么为零，要么为另一个自然数的后继。但是，这种思维方式对学生而言并不自然（大多数人看不到自然数，而是立即想到“哦，一种自我参照的数据类型！”，例如他们学习树的方式）。因此，比其他书本更晚地引入自然递归。只是没那么有趣。

通过这种设置，我们实际上可以看到像阶乘和斐波那契这样的结构递归函数。 Euclid的算法仍然不是结构性的-它非常具有生成性。河内的塔楼坐落在一个有趣的中间地带。但是我们已经知道了为什么这些问题很糟糕，因此无需进一步讨论它们！

递归的力量不仅在于捕获某些数据模式，还在于概括循环。您可以像使用循环一样累积数据，但也可以返回数据，甚至在处理过程中也返回数据。但是，递归甚至比这更有用：您可以相互递归，捕获数据互连的丰富模式。有关此示例的不寻常示例，请参见本文。

肯定是！我试图将几百页内容精简为一个。未蒸馏的溶液可完全免费在线获得。