递归函数

定义

在程序设计中，递归函数指在函数体内直接或间接调用该函数自身的函数。这类函数通常包含两部分：一部分针对规模最小的问题直接给出结果，另一部分把问题缩小后再次调用自身。前者提供出口，后者推动计算向出口靠近。^[1][3]

在数理逻辑与可计算性理论中，递归函数指定义在自然数集合上、未知值可以通过有限次运算归约到已知值的一类函数，也称 μ-递归函数或一般递归函数。它是对“能行可计算”这一直观概念的精确数学刻画之一，与λ演算可定义函数、图灵机可计算函数所指的函数类相同。^[4][2]

原理

递归函数的运行依赖调用栈。每一次递归调用都会在运行栈上建立一个新的栈帧，用于保存本次调用的参数、局部变量和返回位置；调用返回时弹出该帧，控制权交回上一层，上层再取用下层算出的结果继续运算。由于栈空间有限，递归层数过深会导致栈溢出。^[5][6]

以阶乘为例，其递归定义可写为：$fact(n) = 1$（当 $n=0$ 时），$fact(n) = n \times fact(n-1)$（当 $n>0$ 时）。计算 $fact(3)$ 时，函数依次调用 $fact(2)$、$fact(1)$、$fact(0)$，到达基线条件后逐层返回并相乘，最终得到 6。^[5]

flowchart TD

A["fact(3)"] --> B["3 × fact(2)"]

B --> C["3 × 2 × fact(1)"]

C --> D["3 × 2 × 1 × fact(0)"]

D --> E["3 × 2 × 1 × 1"]

E --> F["返回 6"]

递归结构与数学归纳法相对应：若命题对最小情形成立，且由第 $n-1$ 步成立可推出第 $n$ 步成立，则命题对所有情形成立。递归函数同样先确立基线情形，再规定由前一步结果得到后一步结果的规则，因此递归定义的正确性通常用归纳法证明。^[3]

发展历程

20 世纪 30 年代，为回答“什么是可计算的”，数学家给出了若干种彼此独立的刻画。1934 年，哥德尔在普林斯顿的讲演中受埃尔布朗启发，引入了一类可精确定义的函数，称为一般递归函数；1936 年，克林引入 μ-递归函数的概念，并证明它与哥德尔的一般递归函数类一致。^[2][7]

1936 年，丘奇与克林分别发表论文，证明 λ 可定义函数类与一般递归函数类重合；同年图灵提出图灵机并定义了一类可计算函数，1937 年进一步证明图灵机可计算函数类与 λ 可定义函数类一致，从而也与一般递归函数类重合。这些结果使丘奇的论题与图灵的论题合二为一，形成丘奇-图灵论题：能行可计算的函数恰好就是递归函数。^[2][8]

德国数学家阿克曼在 1924 年构造了一个可计算但并非原始递归的数论函数，说明一般递归函数类比原始递归函数类更广；后来这一函数被称为阿克曼函数。莫绍揆于 1965 年借助一般递归式给出了等价定义。^[7][9]

应用

在程序设计中，递归适合处理本身具有递归结构的问题，如树的遍历、图的搜索、目录与文件的枚举等。深度未知的树形遍历用递归描述，代码通常比等价的迭代写法更简短、更接近问题的抽象描述。^[3][10]

经典算法中，汉诺塔、阶乘、幂运算、二分查找、欧几里得算法求最大公约数都有自然的递归写法。汉诺塔的解法可描述为：先将上面 $n-1$ 个盘移到辅助柱，移动最大盘，再把 $n-1$ 个盘移到目标柱。^[1][11]

在理论层面，递归函数为判定问题提供了分析工具：若某问题的特征函数是递归全函数，该问题可完全判定；若是递归部分函数，则只能半判定。这一框架被用于证明某些问题不存在算法解。^[9]

局限

递归写法在时间与空间上往往不如迭代高效。每次调用都要建立栈帧，额外开销随递归深度增长，求解斐波那契数列的朴素递归写法会重复计算同一个小问题，执行时间随规模呈指数增长。^[10][11]

递归深度受运行栈容量限制。缺少基线条件或递归部分没有真正缩小问题时，会形成无穷递归，程序最终因耗尽内存而异常终止。此外，并非所有递归函数都是原始递归函数，阿克曼函数即为反例；全体一般递归函数也不是能行可列的。^[11][7]

丘奇-图灵论题本身无法被严格证明，因为“可有效计算”是直觉概念，该论题至今仍是一个假说，只是尚未发现反例并获得广泛接受。^[8]

参见

• 图灵机 —— 与递归函数等价的一种抽象计算模型。

• λ演算 —— 另一种刻画可计算函数的计算模型。

• 丘奇-图灵论题 —— 断言能行可计算函数恰为递归函数的论题。

• 数学归纳法 —— 递归定义与递归证明所依据的数学方法。

• 调用栈 —— 支撑递归函数运行的数据结构。

• 分治法 —— 常借助递归实现的算法设计策略。