递归 vs 迭代

概述

递归（Recursion）和迭代（Iteration）是表达重复计算的两种基本范式。递归通过函数调用自身来求解子问题，利用系统调用栈保存中间状态；迭代通过循环结构重复执行代码块，显式维护状态变量。二者在逻辑上等价——任何递归都可以转化为迭代，反之亦然——但在代码可读性、空间效率和适用场景上各有优劣。

定义

递归

函数在其定义中直接或间接调用自身。每个递归算法包含基础情形（直接返回结果，终止递归）和递归调用（将问题分解为更小的子问题）。代码结构直接反映问题的数学定义，简洁优雅。例如阶乘：$n!=n\cdot (n-1)!$。

迭代

使用循环结构（for、while）重复执行一段代码。通过显式的状态变量（计数器、累加器等）跟踪计算进度，每次循环更新状态直到满足终止条件。代码通常更贴近底层执行过程。例如阶乘：result = 1; for i = 2 to n: result *= i。

对比维度

维度	递归	迭代
实现方式	函数调用自身	循环结构
状态管理	隐式（系统调用栈）	显式（状态变量）
空间开销	$O(d)$（$d$ 为递归深度）	$O(1)$（通常）
时间开销	有函数调用开销	无额外调用开销
代码可读性	更贴近数学定义	更贴近执行过程
栈溢出风险	深度递归可能溢出	无此风险
终止条件	基础情形	循环条件
典型应用	树遍历、分治算法、回溯	数值计算、线性搜索、累加
转换方法	尾递归优化、显式栈模拟	递推展开
重复计算	朴素递归可能有大量重复	通常无重复计算问题

关键区别

• 递归利用系统调用栈隐式保存状态，迭代显式维护状态变量——这是实现机制的根本区别
• 递归的空间复杂度取决于递归深度（最坏 $O(n)$），迭代通常只需 $O(1)$ 额外空间
• 递归代码更简洁、更贴近问题的数学定义（如阶乘 $n!=n\cdot (n-1)!$），迭代代码更高效
• 尾递归（递归调用是函数最后操作）可以被编译器优化为迭代，空间降至 $O(1)$
• 朴素递归可能产生大量重复计算（如斐波那契的 $O(2^n)$），需要记忆化或转化为迭代来优化

联系

• 递归和迭代在逻辑上等价——任何递归都可以转化为迭代（通过显式栈），任何迭代都可以转化为递归
• 递归定义与数学归纳法对偶：递归定义用于构造，归纳法用于证明
• 递归算法的正确性由数学归纳法保证，复杂度通过递推关系分析
• 分治算法（如归并排序）天然适合递归实现，但也可以用迭代方式实现
• 在实际编程中，选择递归还是迭代取决于问题结构、性能要求和语言特性

参见

• 递归定义 — 递归定义的完整概念卡片
• 递归算法 — 递归算法的完整概念卡片