“递归是如何进入编程领域的”(2014)

到现在为止，很难想象曾经有过这样一段时间，编程中递归的效用甚至可能性都是值得怀疑的。然而，1960年左右的编程社区就是这样。即使是要创建ALGOL 60的委员会在这个问题上也存在分歧。递归是如何进入语言的，这是一个充满阴谋和误解的故事。我第一次看到这个故事是在阅读Gauthier van den Hove优秀的硕士论文时[11]。这也是……章的主题。

在20世纪50年代末，成立了一个委员会来设计一种通用的、与机器无关的编程语言。这样的语言在当时并不是一种多余的奢侈品：程序员使用的是硬件制造商提供的编程系统，这些系统在不同的型号上甚至不统一。Fortran是第一个例外，但当时仍与一家制造商捆绑在一起。LISP是未来事物的先兆：独立于机器，不依赖于制造商。这就是..。

麦卡锡刚刚获得Lisp项目的成功，他对递归充满热情，认为递归是一种优雅的方式，可以让计算机做它们最擅长的事情：每次重复执行相同的代码，并进行适当的修改。事实上，第一个Lisp没有迭代，因此添加线性列表的所有元素的唯一方法是编写一个递归定义的函数。作为ALGOL委员会的成员之一，他提议将递归的可能性作为新语言的一个特征。这个提议..。

反对的理由很多。目前还不清楚它是否可以实现：像Lisp解释器这样的薄薄的学术实验并不是委员会中的德国派别心目中坚实、高效的编译器的权威例子。但委员会成员Naur和van Wijngaarden同意麦卡锡的观点，即递归是一个太诱人的机会，不能错过。范·维恩加登受到了他的助手埃德斯格·W·迪克斯特拉(Edsger W.Dijkstra)的怂恿，后者支持递归……。

Naur是编辑Algol报告最终版本的委员会成员。二十年后，诺尔记得它是这样的[1]：

语言概念的最后一个实质性变化是允许递归过程激活。这件事发生的情况如下。[…]。[O]n大约2月10日[…]。我接到了A.van Wijngaarden的电话，他也代表E.W.Dijkstra发言。他们指出，报告草案中缺少一个重要的定义，即在声明正文内而不是分配的左边部分出现程序标识符的含义(如果有的话)。他们还明确表示……。

事实证明，“在这个问题上有麻烦”。几名委员会成员被骗批准了这份报告的最终版本，其中包括一项很容易被忽视的后期补充，这一补充解决了争议，使争议朝着与他们意愿相反的方向发展。委员会成员F.L.Bauer通过将向语言中添加递归描述为“阿姆斯特丹阴谋”来表达他的抗议[1，附录5]。

Dijkstra在2001年的一次采访中明确表示，鲍尔并不是偏执狂[2]：

递归是重要的一步。它是以一种鬼鬼祟祟的方式推出的。ALGOL-60报告草案在59年12月的最后几周之一传阅。我们研究了一下，发现递归调用几乎是允许的，尽管没有说明。我打电话给彼得·诺尔(Peter Naur)--打到哥本哈根是我第一次打国际电话，我永远不会忘记那种兴奋！--我口述了他的一个建议，建议他把这个建议包括进去。有点像“任何其他事件.。

但是，鲍尔没有实现而迪克斯特拉实现的是什么呢？确实，“递归”是什么意思？仔细观察Naur和Dijkstra的上述证词就会发现，人们谈到了“递归过程激活”，这是一个运行时概念，而Dijkstra谈到了“递归”，它可以被解释为源程序的属性。

有可能在执行期间调用存在较早调用的激活记录的过程。

直接或间接调用Self，可能是通过调用命名为形参的过程。

直接或间接调用Self，或通过调用未命名为形参的过程间接调用Self。

当阿尔戈尔委员会的鲍尔派别发现他们是阿姆斯特丹阴谋的受害者时，定义他们喜欢的阿尔戈尔版本似乎是一件简单的事情：去掉令人不快的判决。他们发现这并没有消除递归。至少不是根据含义1的递归。这是他们想要删除的，因为他们想要静态分配过程激活记录。

ALGOL-60报告发表之后，几次尝试重新定义语言：SMALGOL[3]、ECMA子集[4]和ALGOL子集[5]。这些人在他们的愿望上是一致的