1 基本概念
1.1 定义
递归函数是指在定义或执行过程中会直接或间接调用自身的函数或算法结构。它常用于描述具有重复子结构的问题，通过把整体拆解为规模更小、形式相同的子问题来求解。递归既是一种编程技术，也是一种数学上的定义方式。
在程序设计中，递归函数通常由两部分组成：一部分负责处理当前问题，另一部分把问题转化为更小的同类问题；在数学中，递归定义则强调某个对象如何由较简单的对象逐步构造出来。
1.2 核心特征
递归函数的核心在于“自我引用”和“逐步收缩”。如果没有合理的停止条件，递归过程会持续展开，导致函数无法正常结束。因此，递归设计通常需要同时考虑问题分解方式与终止条件。
1.2.1 自我调用
自我调用是递归最显著的特征。函数在执行过程中再次调用自身，形成层层嵌套的执行链。根据调用方式不同，自我调用可以是直接发生，也可以通过其他函数间接实现。
1.2.2 终止条件
终止条件用于判断递归何时停止。它是递归正确运行的关键，常被称为“递归出口”或“基例”。当问题规模缩小到足够简单时，函数应直接返回结果，而不再继续向下调用。
1.2.3 问题分解
递归通常依赖问题分解思想，即将原问题拆成若干个形式相同但规模更小的子问题。每次递归调用都推动问题向终点逼近，最终由基础情形给出答案，再逐层回溯整合结果。
1.3 递归与迭代的区别
递归与迭代都可用于重复处理数据或步骤，但实现方式不同。递归通过函数自身调用完成任务，逻辑上较贴近数学定义，表达简洁；迭代则依靠循环结构和状态更新，通常更直接，也更容易控制额外开销。
在实际应用中，递归代码往往更容易理解，尤其适合树形结构和分治问题；迭代方案通常更节省栈空间，执行效率也可能更稳定。两者常可互相转换，具体选择取决于问题性质和性能需求。
2 数学基础
2.1 归纳法与递归
递归思想与数学归纳法关系密切。归纳法通常先证明基础情形，再证明如果某个命题对较小规模成立，则对更大规模也成立；递归则对应地把大问题建立在小问题的结果之上。二者都强调从简单情形逐步推导一般情形。
2.2 递归关系式
递归关系式用于描述一个函数值如何由更小输入的函数值决定。它常见于算法分析和数列研究中，例如某些分治算法的运行时间可写成递推式，再进一步求解其增长趋势。递归关系式是分析复杂度的重要工具。
2.3 递归定义
递归定义是用对象自身或同类对象来定义对象的一种方式。它通常包括初始项和生成规则：先给出最基本的元素，再规定如何由已知元素构造新元素。这种定义方式在数论、组合数学和形式系统中非常常见。
2.3.1 自然数上的递归定义
自然数上的递归定义通常先指定最小的自然数，再规定后继关系。例如，先定义 0 或 1 为基本项，然后说明任何自然数都可以通过增加 1 得到下一个自然数。这种方式体现了从基础元素逐步生成整体集合的思路。
2.3.2 结构递归定义
结构递归定义常用于树、表达式、列表等对象。它不只关注数值大小，而是关注对象的构造形式。定义时通常先列出最简单的结构，再说明如何由已有结构组合出更复杂的结构，因此特别适合描述组合对象。
3 计算机科学中的递归函数
3.1 编程实现方式
在编程中，递归函数通常写成“条件判断 + 自身调用”的形式。程序先检查当前输入是否已达到终止条件；若未达到，则将问题规模缩小后再次调用自身。递归实现简洁直观，但也需要留意调用深度和资源消耗。
3.1.1 直接递归
直接递归指函数在体内直接调用自身。例如某些阶乘、树遍历或分治算法的实现，都会在同一函数中再次触发同名调用。它是最常见的递归形式，结构清晰，便于表达自相似问题。
3.1.2 间接递归
间接递归是指函数并不直接调用自己，而是通过其他函数形成循环调用链，最终又回到自身。虽然调用路径更长，但本质上仍属于递归。此类结构常见于相互协作的函数组中。
3.2 调用栈机制
递归执行依赖调用栈。每次函数被调用，系统都会在栈中保存当前运行状态，待子调用结束后再恢复现场并继续执行。正因如此，递归的运行过程具有明显的层次性和后进先出特征。
3.2.1 栈帧
栈帧是调用栈中的基本单元，通常保存局部变量、参数、临时数据等信息。每进入一次递归调用，就会压入一个新的栈帧；当函数返回时，对应栈帧被弹出。递归层数越深，栈帧数量通常越多。
3.2.2 返回地址
返回地址记录了函数执行完毕后应回到的位置。递归函数在多层调用中，每一层都需要保存自己的返回点，以便在子问题求解完成后继续处理当前层逻辑。返回地址保证了递归展开与回溯的正确顺序。
3.3 时间与空间复杂度
递归程序的性能分析通常要同时考虑时间和空间两个方面。时间复杂度取决于递归调用的次数以及每层处理的工作量；空间复杂度则与递归深度和栈占用有关。某些递归虽然代码简洁，但可能带来较高的开销。
3.3.1 递归树分析
递归树分析是研究递归时间复杂度的常用方法。它把每次递归调用看作树中的一个节点，并观察各层节点数量与代价分布。通过计算整棵树的总开销，可以估计算法的总体复杂度。
3.3.2 主定理应用
主定理是求解特定形式递归关系式的经典工具，常用于分治算法分析。它适用于形如“一个问题拆成若干个等规模子问题，再加上额外开销”的递推式。借助主定理，可以较快判断算法的渐近复杂度。
4 典型应用
4.1 数值计算
递归在数值计算中常用于定义规则清晰、层次明显的函数。它尤其适合由初始值逐步扩展得到结果的场景，不过当计算结构过于庞杂时，也可能需要改用更高效的方法。
4.1.1 阶乘
阶乘是递归函数的经典例子。一个整数的阶乘可表示为当前数乘以前一个数的阶乘，直到达到最小基例。该定义简洁明确，能够很好地体现递归“逐步缩小规模”的特点。
4.1.2 斐波那契数列
斐波那契数列常被用于展示递归的直观性与局限性。其后项可由前两项之和定义，因而天然带有递归结构。但若直接采用朴素递归实现，往往会产生大量重复计算，效率不高。
4.2 数据结构遍历
递归在树和图等结构的遍历中非常常见。由于这些结构本身就具有层级或连接关系，递归可以自然地沿着节点关系展开，表达清晰，代码也较易维护。
4.2.1 二叉树遍历
二叉树遍历是递归应用的典型场景。对某个节点进行处理后，再分别递归访问其左子树和右子树，就能完成前序、中序或后序遍历。该方法与树的定义方式高度一致。
4.2.2 图搜索中的递归形式
在图搜索中，递归常用于深度优先搜索等方法。函数从一个顶点出发，访问相邻节点，并继续深入未访问区域。为避免循环访问，通常还需配合标记数组或访问集合使用。
4.3 分治算法
分治算法通过将问题拆解为若干部分分别求解，再合并结果来完成任务。递归是分治思想的自然实现方式，因此二者关系紧密。许多高效算法都采用这种结构。
4.3.1 归并排序
归并排序将序列不断二分，分别排序后再合并。整个过程可以递归地进行：先处理左右两半，再把有序子序列合成为完整结果。它的结构清晰，且具有稳定的时间表现。
4.3.2 快速排序
快速排序同样常以递归形式实现。它通过选取基准元素，将序列划分为两部分，再对两部分分别继续排序。该算法通常较快，但具体性能会受到划分是否均衡的影响。
5 性能与优化
5.1 尾递归
尾递归是指递归调用发生在函数的最后一步，调用完成后不再需要额外计算。若运行环境支持尾调用优化，尾递归可以在一定程度上减少栈开销，使其接近迭代执行的效果。
5.2 记忆化搜索
记忆化搜索通过保存已经计算过的结果，避免重复求值。它常用于存在大量重叠子问题的递归场景，例如某些数列或动态规划问题。通过缓存中间结果，可以显著提升效率。
5.3 递归到迭代的转换
在需要降低栈风险或提高控制精度时，递归常可改写为迭代。转换的关键在于保留原有的状态转移逻辑，并用其他结构模拟函数调用过程。这样既能维持算法思路，又能减少递归带来的局限。
5.3.1 显式栈模拟
显式栈模拟是用程序中的栈结构代替系统调用栈。开发者手动压入和弹出状态，重现递归展开与回溯过程。这种方法适合复杂递归逻辑，也便于更细致地控制执行流程。
5.3.2 循环重写
循环重写是将递归逻辑改写为循环结构，并在循环内维护必要的状态变量。对于一些线性递归或状态较简单的问题，这种方式通常更高效，也更容易避免深层调用带来的风险。
6 常见问题与错误
6.1 无限递归
无限递归指函数不断调用自身而没有正确结束，最终无法正常返回。其常见原因包括终止条件缺失、条件判断错误或问题规模未真正缩小。此类错误会导致程序运行失控。
6.2 栈溢出
当递归层数过深，系统调用栈可能被占满，进而发生栈溢出。高层次递归、输入规模过大或终止条件过晚，都可能引发这一问题。实际编程中需要关注递归深度限制。
6.3 重复计算
重复计算是朴素递归中常见的效率问题。某些子问题会被多次求解，造成时间浪费。典型例子是没有缓存的斐波那契递归，因此常需要借助记忆化或改用其他算法优化。
6.4 递归出口设计失误
递归出口设计不当会导致结果错误或程序无法终止。常见失误包括出口过少、出口条件过宽或返回值设置不合理。一个健全的递归实现，必须保证每条路径最终都能到达正确的终止状态。
7 相关理论
7.1 可计算性理论
在可计算性理论中，递归思想与“函数可由有限规则描述并有效执行”这一主题密切相关。许多经典可计算模型都体现出用基本操作和重复调用构造复杂行为的思路，因此递归是理解计算过程的重要入口。
7.2 λ演算中的递归思想
λ演算强调函数抽象与应用，是现代函数式编程的重要理论基础。递归思想在其中常通过自应用或固定点构造来表达，使函数能够在不依赖外部循环的情况下反复展开自身逻辑。
7.3 形式语言与文法中的递归结构
形式语言和文法中大量存在递归结构。一个非终结符可以被定义为包含自身的产生式，从而生成层次化、可重复扩展的句法结构。这种机制是描述自然语言、编程语言与符号系统的重要工具。