主要观点：递归常与无穷相关，但其起源基于有穷主义。1923 年 Skolem 发展递归函数理论以避免无穷悖论，原始递归由 Dedekind 于 1888 年引入，Gödel 对递归理论贡献大，Rózsa Péter 创造“原始递归”术语。编程语言是传达递归概念的好方式，《The Little Schemer》通过对话教 Scheme 递归。原始递归基于自然数定义，有零规则、后继函数、投影函数及合成、递归操作等。通过这些可构建原始递归函数代数，如加法、乘法、阶乘、幂等，还可定义逻辑相关函数。Hilbert 曾认为所有可计算函数都是原始递归的，但其学生证明错误，如 Sudan 函数和 Ackermann 函数增长超指数。原始递归对应可提前知道搜索范围的函数，一般可计算性范围更广，Turing 完备系统包含不可计算函数，Lisp 基于一般递归但可处理符号。

关键信息：

• 1923 年 Skolem 提出递归函数理论。
• Dedekind 引入原始递归。
• Gödel 对递归理论影响大。
• Rózsa Péter 创造“原始递归”术语。
• 编程语言可传达递归概念。
• 原始递归基于自然数定义及相关操作。
• 可构建原始递归函数代数。
• Hilbert 观点及学生的反驳。
• 不同类型函数的特点及举例。

重要细节：

• 零规则函数((Z))返回 0。
• 后继函数(S inc)将数加 1。
• 投影函数(P i)从序列中选元素。
• 合成操作(C f & gs)将函数 f 应用于 gs 函数结果。
• 递归操作(R n & xs)有边界，初始化后用 g 函数规则计算。
• 如加法(add x y)通过应用后继函数 x 次于 y + 1 实现等。
• Sudan 函数和 Ackermann 函数增长超指数。
• Lisp 基于一般递归处理符号。