编程与软件工程vanemden.wordpress.com
递归是如何进入编程的：一场阴差阳错的喜剧
How recursion got into programming: a comedy of errors
2014 — 2020，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章回顾了 1960 年前后 ALGOL 60 标准制定过程中围绕「递归」的争论：一部分人认为语言应当贴合当时的机器实现，另一部分人以 Dijkstra、Peter Naur 为代表，主张语言设计应当追求数学上的优雅，不必迁就当时的硬件，最终递归被写入报告。文中把这些争论中的误会、人事与妥协讲成一出「错误的喜剧」。
为什么经久不衰：它把今天被视为理所当然的语言特性还原成一场具体的历史争论，让人看到硬件限制、委员会政治与设计品味如何共同塑造了编程语言。
HN 评论精选
递归之争的根源是当时还没有硬件调用栈，支持递归意味着额外成本。
文章没有解释为什么当年人们不愿把递归列为必须支持的特性。很可能是因为「使用调用栈」这个想法本身当时仍有争议。比如在 PDP-8 上，调用约定是把返回地址写进被调用函数前一个内存字里——简单，但基本排除了递归调用。今天我们理所当然地认为 CPU 会提供由 CALL/RET 自动管理的栈指针；在硬件提供之前，编译器得自己实现。所以一旦决定支持递归，你就得引入栈，并给每次函数调用增加一点开销。而一旦有了栈，允许递归就是顺带的事，自然就会支持。
bodyfour查看英文原文
The article doesn't mention why people didn't want recursion to be a requirement. It was probably because the idea of using a call stack was still controversial. For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls. These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you'd end up requiring a stack and adding a small cost to every function call. Once you decide to have a stack, allowing recursion is a freebee so of course you'd include it.
Peter Naur 靠提前写好的草案主导了 ALGOL 60 的方向。
这里有一条很实用的政治建议，出自 Peter Naur：想让委员会按你的想法走，就带着已经做完的大部分工作到场——那份工作会成为之后所有谈判的起点。他对 ALGOL 60 规范的影响，也是他多年后获得图灵奖的重要原因。
lars查看英文原文
This has some solid political advice courtesy of Peter Naur: If you want to get a committee to do what you want, show up with most of the work already done. That work became the starting point for all the future negotiations. And his influence on Algol-60 spec was a strong contributor to him receiving a Turing award years later.
静态活动记录让过程调用等同于 goto，而多年后尾递归又把调用化回了 goto。
我一时很难接受「静态活动记录」这个概念——那样一来「过程调用」就只是个 goto 了。不过我猜我自己写汇编时就是这么做的。讽刺的是，差不多二十年后，动态活动的观念已被充分吸收，以至于可以写出一篇有影响力的论文，论证过程调用（和 lambda）其实可以被看作 goto（通过尾递归）。
gumby查看英文原文
It was hard for a moment to get my head around the idea of static activation records. That makes “procedure call” simply into a goto. I guess I tend to write assembly code this way though. Ironic that almost 20 years later the idea of dynamic activation had been so well absorbed that it was possible to write an influential paper all about how procedure call (and lambda) could be considered a goto (via tail recursion)!
反递归派要语言迁就机器，Dijkstra 派要机器迁就语言， hindsight 证明后者更正确。
我大学上过一门计算机史课程，讨论过这场争议。我的理解是，两派对于 ALGOL 应该是什么样子采取了不同的取向。反递归的一派想设计一门在「当时的机器」上立刻能高效使用的语言，也就是让语言去迁就机器；因为当时没人真正懂如何高效实现递归，所以他们认为不能加。Dijkstra 这一派则认为语言应当尽可能优雅，不必过多顾虑当时机器的局限，先设计出被广泛接受的编程语言，机器设计自然会跟上。我认为在当时的语境下两种观点都成立，但事后看来 Dijkstra 一方更有远见。
ookdatnog查看英文原文
I took a History of CS course in college, where this controversy was discussed. The way I understood it, the two camps approached the question of what ALGOL should be slightly differently. One camp (against recursion) was trying to design a language that would be productive for programming in the (then) here and now, with the machines they had at the time; in other words, the language is molded after the machine. Since efficiently implementing recursion wasn't well understood at the time, adding it to the language was a no-go for them. The Dijkstra side of the argument was that the language should be designed to be as elegant as possible, without much concern for the limitations of the machines of the day. The idea was that, once a broadly accepted programming language was designed, computer designs would follow to support it. I think both are valid viewpoints (especially in context), although with perfect hindsight Dijkstra et al seem to have been the more prescient side.
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选