原始递归——有界循环，总会停机

父级：recursive-functions

原始递归函数类

最小的这样一类函数：它包含基本函数——

• 零函数 Z() = 0、后继函数 S(n) = n+1、投影函数 Pᵢ(x₁,…,xₖ) = xᵢ —— 并且对以下运算封闭：
• 复合（把函数套进函数里）；
• 原始递归：按如下方式定义 f： f(0, x) = g(x) 且 f(n+1, x) = h(n, f(n, x), x)， 即对一个严格递减到基准情形的计数器 n 做递归。

每个原始递归函数都是全函数

每个原始递归函数都在所有输入上停机——它的递归由一个计数器驱动，这个计数器递减到 0，所以不可能无限运行下去。原始递归 = 有界的 for 循环。

涵盖范围与它的上限

加法、乘法、指数、阶乘、有界搜索、素性判定、gcd、元组的编码/解码——本质上每一个"日常"全函数都是原始递归的。

但递归深度总是受输入本身限定：无论怎样嵌套 for 循环，都无法编码一个长度事先未知的搜索。所以这一类并不是全部可计算函数——见证者是 Ackermann's function，它是全函数、可计算，但增长速度比任何原始递归函数都快。要走得更远，需要无界搜索 → general-recursion。