##### 递归函数 - 递归函数 - **递归函数**是通过自身调用自身[[递归]]定义的[[映射]], 是通过基本函数和操作构造的[[计算模型|可计算函数]], 递归函数是从以下基本函数出发, 通过递归规则构造的 - 零函数 - $Z(x) = 0$ 该函数对所有输入都返回 $0$ - 后继函数 - $S(x) = x + 1$ 该函数返回输入的后继值, 即自增 $1$ - 投影函数 - $P^n_i(x_1, x_2, ..., x_n) = x_i$ 该函数返回第 $i$ 个输入变量 - 合成 - 如果 $g$ 和 $h_1, h_2, ..., h_m$ 是递归函数, 则定义 $f(x_1, ..., x_n) = g(h_1(x_1, ..., x_n), ..., h_m(x_1, ..., x_n))$ 也是递归函数 - 原始递归 - 如果 $g(x)$ 和 $h(x, y, z)$ 是递归函数, 则可以定义一个新函数 $f(x, y)$, 允许我们通过前一个值 $f(n, y)$ 递归定义 $f(n+1, y)$, $f(0,y)=g(y)$, $f(n+1,y)=h(n,f(n,y),y)$ - 最小化 - 如果 $g(x, y)$ 是一个递归函数, 则定义 $f(x) = \mu y [g(x, y) = 0]$, 其中 $\mu y$ 表示寻找最小的 $y$ 使得 $g(x, y) = 0$, 这个规则扩展了原始递归函数, 使得递归函数理论能够描述所有图灵可计算函数