递归

递归是一种通过引用同一结构或计算的其他实例来定义结构或进行计算的方法。在计算机科学中，递归过程会直接或间接调用自身，通常用于求解规模较小的子问题，再利用这些子问题的结果求出原问题的答案。在数学中，递归定义通过初始情形以及构造后续情形的规则来确定对象。因此，递归既是一种描述方法，也是设计算法的实用基础。(sicp.sourceacademy.org)

定义与基本情形

能够终止的递归计算通常包含两个部分：基本情形，无需进一步递归调用即可给出答案；以及递归情形，将问题归约为其他实例。这种归约不一定要减小某个数值参数，也可以缩短序列、移除一个组成部分，或深入到结构中较小的部分。关键在于逐步接近一个可以直接处理的情形。(ocw.mit.edu)

例如，对于非负整数 (n)，称为阶乘的函数可以定义为：

[ 0!=1,\qquad n!=n(n-1)!\quad(n>0). ]

相应的伪代码如下：

factorial(n):
    require n 为非负整数
    if n = 0:
        return 1
    return n * factorial(n - 1)

计算 factorial(3) 时，该过程会调用 factorial(2)，接着调用 factorial(1)，再调用 factorial(0)。这些调用逐层返回，提供计算所需的值，最终得到 (6)。输入限制十分重要：如果从负整数开始不断减一，就永远无法到达零。(ocw.mit.edu)

当一个过程调用自身时，就发生了直接递归。当一连串调用最终回到最初的过程时，就发生了间接递归，也称相互递归。递归的本质特征在于过程定义之间的这种循环关系，而不在于调用次数。(sicp.sourceacademy.org)

终止性与正确性

仅有基本情形，并不能保证计算会终止。递归调用必须最终到达该情形。一种常见的终止性论证方法是找出一个非负度量，使其在每次调用时都严格减小，例如尚未处理的元素数量。对于阶乘，这个度量就是 (n)。对于有限结构上的操作，它可以是剩余结构的大小。输入保持不变或缩减方式不当，都可能导致计算无法终止。(ocw.mit.edu)

正确性与数学归纳法密切相关。数学证明先确立基本情形会返回正确答案，再说明较小实例的正确答案能够推出较大实例的正确答案。递归定义用于构造对象或计算其值，归纳法则用于确立这些对象的性质。两种方法都采用“基础情形加递推步骤”的组织方式，但用途不同。(cs.cornell.edu)

执行与内存

许多实现使用调用栈来管理递归执行。每个尚未结束的调用都有一个栈帧，其中保存着继续执行所需的信息，包括局部状态和返回位置。递归调用会增加一个尚未结束的调用；调用返回后，其调用者便可继续执行。在普通的递归阶乘计算中，各层调用者会保留尚未完成的乘法运算，直到最内层调用结束。(sicp.sourceacademy.org)

内存消耗取决于同时处于活动状态的调用数量的最大值，而不只是调用总次数。递归过深可能耗尽可用的栈空间。此外，除了栈帧本身，局部对象和输入的副本也可能占用额外内存。这些开销取决于具体过程以及编程语言的实现。(ocw.mit.edu)

递归、迭代与尾调用

迭代通过连续更新状态来表达重复操作，通常使用循环。递归和迭代可以描述等价的计算，但源代码的形式不一定决定其内存使用方式。递归过程也可能产生一种计算进程，其完整状态仅由一组固定数量的变量构成。(sicp.sourceacademy.org)

尾调用是指调用者无需进一步计算，就能直接返回其结果的调用。在尾递归阶乘中，累积器保存已经算出的乘积，递归调用则接收更新后的累积器。前面的阶乘示例不是尾递归，因为递归调用返回后仍需进行乘法运算。支持恰当尾调用的实现可以避免保留不断增长的栈帧链。仅有尾递归的语法形式，并不保证会进行这种优化。(sicp.sourceacademy.org)

复杂性与重复子问题

递归算法的计算复杂性取决于其调用结构，以及每次调用内部所执行的工作。在算术运算成本为常数的模型下，用大O记号表示，普通递归阶乘需要 (O(n)) 次运算和 (O(n)) 的栈空间。其运行时间可以用递推关系表示，例如 (T(n)=T(n-1)+O(1))。如果明确计入对越来越大的整数进行算术运算的成本，所得开销就会有所不同。(cs.cornell.edu)

直接按照 (F(n)=F(n-1)+F(n-2)) 递归计算斐波那契数列，会反复求解相同的较小实例。其运算次数呈指数增长，但最大调用深度仅呈线性增长。这一区别说明，计算工作总量与同时所需的存储空间是两个不同的概念。(sicp.sourceacademy.org)

当计算包含重叠子问题时，记忆化会保存已经算出的结果，以便重复使用。将其应用于斐波那契数列，可以把需要计算的不同实例数量降至线性规模。这种结果复用是动态规划的核心；朴素斐波那契递归的低效源于重复工作，而非仅仅因为它调用了自身。(cs.cornell.edu)

递归结构与应用

递归天然适合层次化的数据结构。例如，一棵树包含若干子树，而处理整棵树的操作也可以用于处理这些子树。递归过程可以合并各子树的处理结果，使计算的组织方式与数据结构相吻合。循环引用需要格外谨慎地处理：如果没有停止机制，沿着这些引用继续处理，可能永远不会结束。(sicp.sourceacademy.org)

分治法算法同样会将问题归约为较小的实例，再合并它们的答案。递归提供了一种直接表达这种组织方式的方法，而复杂性分析则用于判断这种分解是否确实能带来高效的计算。(ocw.mit.edu)