递归算法性能需实测验证，应控制变量、对比等价迭代实现，并用语言专用工具：python用timeit、java用jmh、c++用google benchmark、rust用criterion；测试需统一输入、排除i/o、注意栈限制、区分缓存状态，同时关注栈深度、内存占用及时间分布，结合理论分析归因。
递归算法的执行效率不能只靠理论推导，必须通过实际运行来验证。关键在于控制变量、消除干扰、多次采样，并对比等价的非递归实现。
选择合适的测试工具
不同语言有成熟且差异明显的基准测试方案：
- Python 推荐用 timeit 模块，它自动处理循环调用、垃圾回收干扰和多次运行取平均，比手动用
time.time()更可靠；Jupyter 中直接用%%timeit最方便 - Java 强烈建议使用 JMH（Java Microbenchmarking Harness），它能规避JIT预热、指令重排序等常见陷阱，避免“假快”结果
- C++ 常用 Google Benchmark，支持自动调节迭代次数、统计标准差、输出纳秒级耗时，还能测量内存分配次数
- Rust 推荐 Criterion 库，它基于统计建模分析性能变化，能检测微小但真实的性能退化，比标准库
test::Bencher更严谨
设计可比的测试用例
评估递归效率，必须和功能完全一致的迭代版本对照，且输入数据严格相同：
- 统一输入规模：比如都测试计算第 35 项斐波那契数，而不是一个用 n=30、另一个用 n=40
- 排除 I/O 和初始化开销：把纯计算逻辑单独封装，基准测试中只测核心函数调用，不包含 print 或 list 创建
- 注意栈深度限制：Python 默认递归深度约 1000，测试大输入前需用
sys.setrecursionlimit()调整，否则直接报错而非反映真实耗时 - 对带缓存的递归（如记忆化斐波那契），要区分“首次运行”和“重复运行”，因为后者受益于已缓存结果
关注递归特有的性能维度
除了总耗时，还需观察递归引入的额外开销：
-
调用栈深度：递归每层都压入新栈帧，深度过大易触发栈溢出。可用
threading.stack_size()（Python）或 JVM 参数（Java）辅助观察 - 内存占用增长：递归版本常比迭代多消耗 O(n) 空间（n 为深度），而迭代可能只需 O(1)。用 memory_profiler（Python）或 VisualVM（Java）实测更直观
- 最坏/平均情况分离：例如随机化快速选择算法，应多次运行取时间分布（中位数、95分位数），而非只看单次结果
结合理论与实测做归因分析
单纯知道“递归慢”没意义，要定位慢在哪：
- 如果递归版比迭代版慢 10 倍以上，大概率是重复子问题未缓存（如朴素斐波那契）；加上 @lru_cache 后再测，差距通常大幅缩小
- 若两者耗时接近，但递归版内存高、栈深大，说明问题不在 CPU 而在资源模型——这时即使时间达标，生产环境仍可能因栈溢出失败
- 绘制输入规模 n 与执行时间的关系图，验证是否符合预期复杂度（如 O(2ⁿ) 指数曲线 vs O(n) 线性曲线）
