原始递归函数

定义

原始递归函数接受一个或多个自然数作为输入，返回一个自然数作为输出。原始递归函数由如下公理给出：

基本情况
1. 常值函数：0元常数函数 \(0\) 是原始递归的
2. 后继函数：1元后继函数 \(S\) ，它接受一个参数并返回皮亚诺公理给出的后继数，是原始递归的。
3. 投影函数：对于所有 \(n\ge1\) 和每个 \(1\le i\le n\) 的 \(i\) ， \(n\) 元投影函数 \(P_i^n\) 接受 \(n\) 个参数并返回第 \(i\) 个参数，是原始递归的。
运算
1. 复合：给定 \(k\) 元原始递归函数 \(f\) ，和 \(k\) 个 \(m\) 元原始递归函数 \(g_1,\cdots,g_k\) ，则 \(m\) 元函数 \(h\) 定义为 \(h(x_1,\cdots,x_m)=f(g_1(x_1,\cdots,x_m),\cdots,g_k(x_1,\cdots,x_m))\) ，是原始递归的。
2. 原始递归：给定 \(n\) 元原始递归函数 \(f\) 和 \(n+2\) 元原始递归函数 \(g\) ，则 \(n+1\) 元函数 \(h\) 定义为 \(h(x_1,\cdots,x_n,y)=\begin{cases}f(x_1,\cdots,x_n)&\text{if }y=0\\g(x_1,\cdots,x_n,y-1,h(x_1,\cdots,x_n,y-1))&\text{if }y>0\end{cases}\) ，是原始递归的。

一个函数是原始递归的，当且仅当它是基本情况中的函数，或可以从基本情况通过有限次复合和原始递归得到。

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

令 \(f: ()\to 1\) ， \(g: (x, y)\to (x + 1) * y\)

可证明 ~~（略）~~ \(f\) 和 \(g\) 都是原始递归的。

发现 \(factorial\) 满足 \(factorial(0)=f()\) ，且 \(factorial(S(n))=g(n, factorial(n))\)

因此 \(factorial\) 是原始递归的。