计算机科学导论中的迭代和递归

教育部正在推进基础学科系列“101计划”。最近，我浏览了该计划中的教材《计算机科学导论——计算+、互联网+与人工智能》(战德臣、张丽杰等编，2025年高等教育出版社出版)。此书倡导了“计算思维”这种新的视角；就内容编排而言，它与美国一本非常流行的计算机科学概论教材基本相似：“Computer Science: An Overview” (J. Glenn Brookshear & Dennis Brylow, 13rd Edition published in 2019)——此书于1985年首次出版，迄今已出至第13版，这足以证明其广为流行。此书有中文版：《计算机科学概论（第13版）》[美]J.格伦•布鲁克希尔&丹尼斯•布里罗著 ，刘艺、吴英、毛倩倩译，2022年人民邮电出版社出版。

总的来说，战德臣等编的《计算机科学导论》是一本优秀的教科书。但是在叙述迭代与递归时，此书的表述并不完全准确。迭代和递归是计算机中执行重复性任务的两种模式（或称方式、控制结构）：从可计算性的角度来看，它们是完全等价的。但是此书有以下两处不正确的陈述：

此书第142页：

上述说法不正确，因为：阿克曼函数当然可以用迭代方式实现，并非必须通过递归来实现/执行。如果你愿意，问问某些AI 工具：它们都能对 Ackmann 函数给出迭代解决方案。

此书第150页：

上述说法不正确，因为：对于同一算法/任务，迭代实现的程序和递归实现的程序是可以相互转换的。

相比而言，Brookshear & Brylow’s《计算机科学概论（第13版）》关于迭代与递归的陈述是正确的。作为扩展阅读材料，此书还包括：《附录E： 迭代结构与递归结构的等价性 》。

从更深一层次来说，迭代与递归等价这一命题包含在邱奇-图灵论题（Church-Turing Thesis）之中。邱奇-图灵论题包含以下两个方面：

直观等价：它将日常生活中非形式化的“有效方法”或“直觉上的算法”等同于严格数学定义的图灵可计算函数——即：任何在算法上可计算的问题同样可由图灵机计算。这一部分是无法证明的，因此可以说是一个假设。

模型统一：邱奇的λ-演算、图灵的图灵机以及克莱尼的递归函数，在计算能力上是完全等价的。这一部分已在20世纪30年代由丘奇、图灵等人严格地证明；这就包含：迭代结构与递归结构的等价性。

当然，采用迭代还是递归方式实现某算法/任务/程序的难易程度，以及生成的程序（代码）的执行效率，既取决于问题类型也取决于编程环境或工具。现代高级编程语言（如 Python, C++, Java）会自动处理函数的递归调用（包括函数调用机制中的堆栈），对于某些具有递归性质的算法/任务/程序，编写递归函数或过程确实要容易得多；而早期的编程语言（如 BASIC）并不支持函数的递归调用，对于相同的算法/任务/程序，采用迭代方式并显式管理堆栈可能会更容易一些。

迭代与递归、它们的等价和相互转换、以及邱奇-图灵论题是计算机科学中的核心概念与结论。如果您教授《计算机科学导论》这样的课程，希望您能向学生传授这方面正确的内容。

支持单位：