主题
Search

原始递归函数

正如 Meyer 和 Ritchie (1967) 首次展示的那样，do 循环（具有固定的迭代限制）是 while 循环的特例。仅使用 do 循环即可实现的函数称为原始递归函数。（相比之下，可计算函数 可以使用 for 循环和 while 循环的组合，或仅使用 while 循环进行编码。）原始递归函数的示例包括 幂、最大公约数 和 p_n（给出第 n 个 素数 的函数）。

阿克曼函数 是 良定义 全函数 的最简单示例，它是 可计算的 但不是原始递归的，这为 1900 年代初期认为每个 可计算函数 也都是原始递归函数的观点提供了反例 (Dötzel 1991; Wolfram 2002, p. 907)。

另请参阅

阿克曼函数, 可计算函数, 一般递归函数, 递归函数, 全函数

使用 Wolfram|Alpha 探索

参考文献

Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2, 16-17, 1991.Meyer, A. and Ritchie, D. "The Complexity of Loop Programs." Proc. 22nd National ACM Conference. Washington, DC: pp. 465-470, 1967.Péter, R. Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 907, 2002.

在 Wolfram|Alpha 上被引用

原始递归函数

如此引用

Weisstein, Eric W. "原始递归函数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PrimitiveRecursiveFunction.html

主题分类