递归函数是一种通过规则刻画的函数,这些规则允许它的值依赖于同一函数的其他值,或依赖于与它一同定义的函数。在编程中,这个术语通常指执行过程中直接或间接调用自身的函数。在可计算性理论中,它有更为具体的数学含义:递归函数是通过形式化规定的运算得到的函数,这些运算刻画了有效计算。这两种含义密切相关,但并不相同。程序即使不包含自调用,也可以计算递归函数;而自指方程未必能确定一个可有效计算的函数。
递归函数将数学定义、可执行过程与机械计算的极限联系起来。它们为算法、编程语言的解释以及有关软件的证明提供了基础。递归函数理论区分了总能返回结果的计算与可能无限持续下去的计算;而在实际应用中,递归则为处理嵌套表达式、分支结构,以及可分解为更小实例的问题提供了一种自然的方法。
历史发展与术语
递归定义的历史远早于电子计算。人们常用一个初始值以及求取后续值的规则来规定算术运算和数列。例如,非负整数上的阶乘函数由下式确定:
这类定义用有限的描述刻画了无穷多个值。它们在数学上是否成立,并不只取决于自我引用,而在于是否具有一种结构,使每个所需的值都能由已经确定的值来确定。
十九世纪末至二十世纪初,数学逻辑日益将计算规则本身作为研究对象。理查德·戴德金关于自然数的工作,为通过递归定义函数提供了重要框架。二十世纪二十年代,与索拉尔夫·斯科伦及大卫·希尔伯特的数学基础研究纲领相关的工作,考察了若干受限形式的有效定义。这些研究促成了如今所谓的原始递归函数这一函数类的形成。威廉·阿克曼于1928年构造出了一个不属于该类的可计算函数,表明一种尤为自然的递归模式并不能涵盖所有有效的数值计算过程。
二十世纪三十年代,雅克·埃尔布朗、库尔特·哥德尔和斯蒂芬·克利尼的工作推动了更广泛的一般递归函数概念的发展。克利尼确立了一些重要的结构性结果,将递归定义、形式演算以及计算的数论描述联系起来。与此同时,艾伦·图灵于1936年独立提出了他的机器模型,阿隆佐·丘奇则发展了一套基于λ演算的理论。等价性结果表明,在适当编码下,这些看似不同的方法刻画的是同一类数值函数。这些方法殊途同归,成为支持丘奇—图灵论题的核心证据。
这些术语的含义仍取决于语境。在经典递归论中,“递归函数”通常指全可计算函数,而“部分递归函数”则明确允许某些输入的结果无定义。有些文献用“一般递归”来区分完整的可计算函数类与其中的原始递归子类。然而,在软件讨论中,“递归函数”通常指子程序的组织方式,而不是对它所计算的数学函数进行分类。因此,一个以迭代方式实现乘法的程序,即使源代码中没有递归调用,计算的仍是数学意义上的递归函数。反过来,一个在某些输入上陷入无限循环的递归程序,在其声明的输入域上计算的只是一个部分函数。
原始递归与数值函数的构造
原始递归函数由少量初始函数通过复合和一种受限的递归模式构造而成。标准的表述从零函数、后继函数 和投影函数出发:
复合允许将先前构造的函数的输出用作另一个函数的自变量。原始递归则通过如下形式的等式引入函数 :
其中, 和 是已有的函数。
关键限制在于,递归调用所使用的自然数自变量必须是当前值的直接前驱。只要各组成函数都是全函数,这一限制就能保证计算对每个输入都在有限步内终止。加法可定义为
随后可以通过反复相加定义乘法,通过反复相乘定义幂运算,并通过将前一个数的阶乘乘以当前数来定义阶乘。这些构造说明,少量简单的初始运算就能生成一个庞大的函数族。
这一函数类的范围远不止简单的算术运算。它包括比较、截断减法、有界求和与求积,以及在将有限字符串和序列编码为自然数后对这些对象进行的许多运算。有界搜索可以逐一检查由自变量给定的界限以下的所有候选值,并记录是否已出现符合条件的候选值。由于尝试次数受一个已知的有限界限约束,这类搜索可以用原始递归来表达。同一原理也支持对机器运行指定步数的模拟。
每个原始递归函数都是全函数,但并非每个全可计算函数都是原始递归函数。阿克曼函数的一种常见双自变量形式满足
可以利用自变量对上的良基序证明其计算必然终止,但其增长最终会超出相关层级中原始递归函数所能达到的界限。这个例子区分了两个容易混淆的问题:一个函数即使具有总能终止的算法,也未必能仅通过原始递归来表达。因此,原始递归刻画的是有效过程中的一个稳健且在数学上受到严格约束的子类,而不是所有必然终止的递归程序的同义词。
部分递归函数与无界搜索
为了刻画一般的计算,可以在原始递归的基础上加入极小化,通常用希腊字母 表示。对于全数值函数 ,表达式
表示使 成立的最小非负整数 。算法可以依次检验 来计算这个值。如果不存在合适的 ,搜索就永远不会返回结果。与有界搜索不同,无界极小化引入了不终止的可能性。
当搜索所涉及的函数本身是部分函数时,通常的定义还要求此前的所有检验都终止,并得到非零值。更确切地说,只有当对 的检验得到零,且此前的每一次检验都得到有定义的非零值时,结果才是 。如果搜索在某个更早的候选值上陷入停滞,就不能跳过该候选值继续搜索。这一细节确保它对应于一种有效的顺序执行过程,而不是一种能够判断计算最终是否会结束的假想操作。
包含初始函数,并且对复合、原始递归和极小化封闭的最小函数类,就是部分递归函数类。部分函数 对某些输入赋予数值结果,而对其他输入则无定义。无定义并不是一种额外的数值输出,而是意味着相应的计算不会产生值。全递归函数是这个函数类中定义域为整个 的成员。因此,用编程术语来说,返回一个明确的错误值与永远运行下去是两种不同的行为。
即使主要关注的是全函数,部分性也不可或缺。通用求值器必须能够模拟不终止的程序,而不受限制的搜索可能对某些输入成功,对另一些输入却无法成功。克林的正规形定理尤其清楚地揭示了这种关系。在一种标准表述中,每个部分递归函数都可以表示为
其中, 是一个原始递归谓词,用于验证一个经过编码的终止计算,而 则提取该计算的输出。这里,极小化选出满足该谓词的最小编码。这样,检验一个给定计算所需的有界机械操作,就与寻找一个成功计算所需的、可能无界的搜索区分开来。
机器计算、通用性与不可判定性
部分递归函数与图灵机可计算的数值函数完全一致,也与其他标准模型中所表示的函数完全一致,这些模型包括适当的寄存器机和 λ 演算。这些都是数学上的等价性定理:一种形式体系中的计算可以转换为另一种形式体系中的计算。相比之下,断言这些等价的形式体系涵盖了所有可有效计算的函数,就是丘奇—图灵论题。这是在基础层面上将两种概念等同起来,而不是针对一个已独立形式化、涵盖所有可能有效方法的概念所证明的定理。
有限描述可以编码为自然数。为程序赋予编码,便得到部分可计算函数的一个枚举:
通用函数接受程序编码 和输入 ,然后模拟 所表示的计算。这在数学上对应于通用解释器。这一枚举允许重复,因为不同的程序可能计算同一个函数;其中也包含在某些输入乃至所有输入上均无定义的程序。
通用性揭示了程序分析的局限。停机问题问的是:一个已编码的程序在给定输入上最终是否会停机。其不可判定性可由对角论证得出:假如存在一个停机判定程序,就可以利用它构造出另一个程序;当这个构造出的程序以自身编码为输入时,其行为会与判定程序的预测相矛盾。一个相关论证说明,不可能存在一个全可计算函数,通过一个仅由全函数构成的有效列表,通用地求出所有全可计算函数的值。如果 是这样一个全求值函数,那么 就是全可计算的,却在每个所列函数自身的索引处都与该函数取值不同。
递归函数也可用于刻画判定问题和识别问题。当一个自然数集合的成员资格特征函数是全递归函数时,该集合就是可判定的。当一台机器能够识别一个集合的成员,而在输入非成员时可能永远运行下去,该集合就是可计算枚举集;等价地,它是某个部分可计算函数的定义域。一个集合可判定,当且仅当它及其补集都是可计算枚举集。这些区别解释了为什么一个最终能发现肯定答案的过程,不一定能提供获得否定答案的方法。它们也表明,不可判定性涉及的是统一算法是否存在,而不只是某种具体实现使用不便或运行时间过长。
编程中的递归定义
在编程语言中,直接递归是指函数调用自身。阶乘的实现通常先判断输入是否为零;若不为零,则返回 与以 为参数的调用结果之积。这一判断提供了基本情形,而逐步减小的参数则引导执行过程趋向该情形。这个定义在非负整数上有意义,但并不自动适用于所有机器整数。如果没有适当的输入条件,负数参数可能会使执行过程离基本情形越来越远;而即使输入是有效的非负数,固定位宽的算术运算也可能产生整数溢出。
间接递归或相互递归是指两个或更多函数彼此调用。例如,可以通过将正数参数减一后交换角色,来定义判断偶数和奇数的谓词。更复杂的例子出现在解析器中:一个过程识别表达式,另一个过程识别项,其他过程则处理带括号的表达式或参数列表。此时,相关的递归单元是一组定义,而非单个函数。如果只分析每个过程是否直接调用自身,就会漏掉这些调用循环。
结构递归遵循数据结构的组织方式。处理列表的函数会单独处理空列表,并将首个元素与对剩余部分递归处理所得的结果相结合。处理二叉树的函数会处理空树或叶节点,并对内部节点的子节点进行处理。这些定义与输入类型的构造方式相对应。它们在函数式编程中很常见,模式匹配往往会明确展现这种对应关系;不过,命令式语言和面向对象语言也同样可以采用这种方法。
并非所有递归都会缩减输入中已有的组成部分。生成式递归会构造新的子问题,例如快速排序先将序列分区,再对所得各部分递归排序。嵌套递归将一次递归调用的结果用作另一次递归调用的参数。高阶函数可以将递归操作作为值传递,从而隐藏或显露递归结构。实际的区别不只在于函数名是否出现在自身的函数体中,还在于各次调用之间的依赖关系如何组织。
递归定义还依赖于求值规则。在严格求值语言中,通常会先对参数求值,再执行调用;在非严格求值语言中,参数则可能直到被需要时才求值。如果某个原本会导致发散的部分始终未被用到,那么一个在某种求值策略下发散的递归表达式,就可能在另一种策略下得到结果。因此,在描述递归函数计算什么时,必须区分数学方程、程序文本以及特定语言的运行时行为。
终止性、归纳法与正确性
要证明递归函数会终止,仅有一个基本情形分支还不够。每条继续递归的执行路径都必须朝着能够返回结果的情形推进。一种标准方法是为每次调用赋予一个取自良基序的值;所谓良基序,就是不存在无限严格下降链的序关系。如果每次递归调用都会使这个值减小,就不可能出现无限的调用序列。对于自然数上的阶乘函数,参数本身就可以作为这一度量。
更复杂的函数需要更丰富的度量。具有两个参数的函数可以按字典序递减:要么第一个分量减小,要么第一个分量保持不变,而第二个分量减小。二元阿克曼函数就可以利用这种序关系来证明终止性。在树上的递归中,真子树关系提供了递减的依据。在某些算法中,无论是单个参数还是固定的参数元组,都看不出明显的递减,但由待处理任务构成的多重集或其他抽象度量却会递减。这些技术能够区分真正的推进与表示形式上的表面变化。
正确性证明往往通过数学归纳法与递归定义相呼应。要证明列表长度函数返回的是元素个数,基本情形需要证明结论对空列表成立。归纳步骤则假设函数对列表尾部的计算是正确的,并证明在其结果上加一就得到整个列表的长度。对于会构造子问题的算法,强归纳法可能更合适:假设正确性对所有更小的输入成立,而不只是对紧邻的前驱成立。相互递归可能需要对多个性质进行同时归纳。
形式验证区分部分正确性与完全正确性。部分正确性是指:如果执行在给定前置条件下终止,那么结果就满足规约。完全正确性还要求执行必须终止。递归定义的函数即使满足一个看似充分刻画返回值的方程,也仍可能在某些允许的输入上无法返回。要确立这两种性质,就必须分别关注功能规约与递减度量。
在证明助手中,例如支持依赖类型的系统,不能直接将不受限制、可能不终止的计算作为普通的证明生成计算纳入逻辑核心。因此,系统通常通过结构递归、良基递归或其他受控机制来接受定义。当递减关系在语法上并不明显时,Lean证明助手等系统可能会要求提供终止性证明。对于不受限制的程序,这类检查必然是不完备的:一个会终止的计算,其终止性证明可能超出自动检查器的能力。因此,自动终止性检查未通过,本身并不能说明程序不会终止。
运行时执行与尾调用
递归的常规实现使用调用栈。每个尚未返回的调用都有一条活动记录,其中包含参数值、局部变量、返回地址以及保存的机器状态等信息。当一个调用发起对另一个函数的调用时,后者会获得自己的活动记录。被调用函数返回后,程序会回到调用者中继续执行。因此,递归调用通常并不共用同一组可变的局部变量,而是创建彼此独立的调用实例,不过这些调用实例可能引用共享对象。
在直接实现的阶乘函数中,递归调用计算较小数的阶乘时,乘法运算会一直等待其结果。因此,计算 的阶乘时,会先形成一条由大约 个尚未返回的调用实例组成的链,然后再逐层返回。如果栈的存储空间有限,足够深的递归就可能将其耗尽。这是实现上的限制,并不意味着该数学函数未定义。可用的递归深度取决于运行时环境、栈帧大小、优化方式和平台,而不是某个普遍适用的递归深度上限。
如果一个调用的结果直接成为调用者的结果,而调用者无须再做任何其他工作,那么这个调用就处于尾位置。使用累加器的阶乘函数可以定义为
并通过 得到阶乘。此时,递归调用就是最后一步计算。通过尾调用优化,实现可以复用当前的活动记录,而不必继续扩展栈。这种变换消除了栈的增长,但并没有消除算术运算本身的工作量,也没有消除存储越来越大的整数所需的空间。
尾调用的行为因语言及其实现而异。Scheme 要求正确支持尾递归,而许多其他语言的实现只提供有限的优化,或者根本不普遍保证进行此类优化。异常处理区域内的调用、调试需求或不兼容的调用约定,都可能使优化变得复杂。因此,除非语言或实现保证了相应行为,否则不能仅凭源代码中的调用处于尾位置,就认定它只使用常量大小的栈空间。
通过显式存储尚未完成的工作,也可以将递归转换为迭代。迭代式遍历可以维护自己的栈,而续延传递变换则将余下的计算表示为显式的续延。蹦床机制反复执行对后续步骤的描述,而不是进行深度嵌套的调用。这些技术只是将控制信息转移到别处,并不一定会消除它。对于具有大量待处理分支的计算,即使机器调用栈保持较浅的深度,显式维护的工作结构仍可能显著增长。
计算成本与重复子问题
递归定义在形式上简洁,并不意味着计算效率高。标准的斐波那契数列递归定义为
其中只有两次递归调用,但直接实现时会反复求解相同的子问题。调用次数随 呈指数增长,数量级为 ,其中 。然而,最大递归深度仅呈线性增长。这个例子说明,总计算量与同时处于活跃状态的递归状态量是两个不同的概念。
记忆化以参数为索引存储计算结果,使重复的请求能够复用已有结果。将其用于斐波那契数列计算,可将不同子问题的数量减少到 ;直接采用表格存储的版本需要线性次数的加法和线性存储空间。自底向上的动态规划实现按照预先确定的顺序计算同一依赖结构,并且可以只保留最近的两个值。这些算术运算次数的估算假设每次加法的成本为常数;斐波那契数的精确值所需的位数与 成正比,因此,位级运算成本会随输入规模增大而上升。
递归在分治法算法中尤为有效。归并排序将输入分成两部分,分别排序,再合并结果。忽略取整和基本情形的细节,其运行时间满足如下形式的递推关系:
由此可得时间复杂度为 。快速排序在划分均衡时具有类似的递推关系,但极不均衡的划分可能导致平方级时间复杂度和线性递归深度。因此,仅凭调用结构无法确定唯一的复杂度界;对划分规模的假设也很重要。
空间开销必须单独计算。一个递归划分均衡的算法可能只需 个活跃栈帧,却同时分配了很大的中间数组。反过来,一种不分配任何新数据结构的遍历算法,在链状树上仍可能占用 的栈空间。精确的空间复杂度分析会区分输入存储、输出存储、辅助堆对象和栈消耗。同样,时间复杂度取决于递归树各节点所执行操作的成本,而不只是递归调用的次数。
递归子问题有时可以并发执行,这使递归与并行计算联系起来。此时,性能既取决于总计算量,也取决于最长依赖链的长度,后者通常称为跨度(span)。相互独立的分支提供了并行机会,但任务创建、同步、内存数据传输以及负载不均衡都会带来成本。过细的递归划分可能只会增加额外开销,而不能减少有效计算量,因此,实际实现通常会在子问题规模低于某个选定阈值时切换为顺序执行的方法。
不动点与递归方程的含义
递归方程可以理解为一种不动点规约。以阶乘为例,定义算子 ,将候选函数 映射为一个新函数:
满足阶乘方程的函数是不动点,因为 。这种表述将定义的主体与自引用分离开来,为递归程序的一般性数学处理提供了基础。
并非每个自引用方程都能确定唯一且有用的函数。方程 没有施加任何约束,而 在通常的整数值全函数中无解。编程语言语义学通常引入一个记作 的未定义元素,用来表示计算不终止或没有结果。在偏函数的一种适当序关系下,处处未定义的函数所包含的信息最少。这样,当相关数学条件成立时,就可以将递归定义的含义确定为其最小不动点。
对于适当的带底元的域上的连续泛函,这个最小不动点可以通过逐次近似的上确界得到:
对于阶乘,第一个有用的近似确定输入为零时的结果,下一个近似确定输入为一时的结果,后续近似则确定更大输入的结果。这一构造解释了如何通过有限层次的计算逐步得到一个定义在无限输入集合上的数学函数。这里的连续性指的是保持信息递增过程的极限,而不是初等微积分中实值函数的连续性。
在 λ 演算中,不动点组合子无需为递归定义的函数赋予内置名称,就能表达递归。适当的组合子 满足如下形式的关系:
实际的求值行为取决于归约策略;适用于非严格策略的组合子,在严格求值语言中可能需要调整。这再次说明,仅凭一个等式恒等关系,并不能判定执行过程是否终止。
一个相关但不同的结果是克林递归定理。按照一种标准表述,对于程序索引上的每个全可计算变换 ,都存在一个索引 ,使得
这里的相等指所计算的偏函数相等,并不一定意味着源代码或程序编号相同。该定理将一种计算中的自引用形式化,并为涉及程序获取或操作其自身描述的表示的构造提供了基础。不应将它与普通的递归调用混为一谈,也不应将它理解为保证任意递归过程都会终止的定理。
在语法、结构化数据和无限对象中的应用
递归函数尤其适合处理以递归方式定义的对象。在编译器中,抽象语法树通过嵌套的构造器来表示表达式和语句。求值器可以为字面量返回一个数值,将递归求得的操作数值组合起来以计算算术表达式,并为绑定构造扩展环境。常量折叠之类的变换也会沿树向下遍历,用简化后的子表达式重建这棵树。程序的控制结构由此与所处理语言的语法结构相对应。
语法分析是另一个主要应用领域。递归下降分析器通常为每个相关的语法类别设置一个函数,函数间的调用则体现语法成分的组合关系。例如,因子可以是数值字面量,也可以是括号括起的表达式,而表达式则包含由运算符连接的项。如果直接实现“表达式是一个表达式后接一个加号和一个项”这样的左递归规则,朴素的自顶向下分析器就会在不消耗任何输入的情况下不断递归。此时需要改写文法,或采用其他语法分析算法。这个例子说明,有效的递归规约并不一定能直接转化为合适的递归执行策略。
树的子节点关系不含环,因此支持结构递归;但处理一般的图时,还需要额外留意。深度优先搜索可以递归访问相邻顶点,前提是记录已访问过的顶点,以免陷入无限循环。目录遍历也可能因符号链接而遇到类似问题。共享的子结构还会改变计算成本:如果一个结构表示为有向无环图而不是树,朴素的递归遍历就可能多次处理同一个节点。记录已访问的节点或缓存结果,可以让计算依据图中节点的实际身份进行,而不是将展开时反复出现的同一节点当作不同节点处理。
递归分解也用于计算机图形学、空间索引、符号代数和自动推理。光线追踪器可以递归追踪反射光线或透射光线,通常会限制递归深度或光线贡献。定理证明器可以递归地将目标分解为子目标,但分支搜索会引出搜索顺序和完备性等问题,超出了简单结构下降所涉及的范围。即使每次展开都有明确的机械执行规则,无限分支仍可能使深度优先策略无法找到其他分支上的解。
无限数据引出了与递归相关的余递归概念。余递归定义并非不断消耗有限对象直至达到基本情形,而是逐层生成流等无界对象。其运行时的核心要求通常是生产性:任何所需的有限部分,都应能在有限次计算后产生。流生成器无须整体终止,也能提供有用的结果。这与失控的递归循环不同:后者可能无限运行,却始终不产生预期输出中任何可观察的部分。