深入浅出：递归函数的时间复杂度分析与示例
温馨提示：
本文最后更新于 2025年07月20日，已超过 5 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
1. 什么是递归及其时间复杂度
递归（Recursion）是函数调用自身来解决问题的编程技术。时间复杂度分析需考虑每次调用的额外工作量、递归深度以及分支数目。
“递归结束的条件”称为递归出口，若出口设置不当可能导致无限循环或栈溢出。 (Hexo)
2. Master 定理：分治算法的利器
对于形如：
T(n) = a · T(n/b) + f(n)
的递归式，Master 定理可直接给出三种情形的渐近解：
- 若 $f(n)=O(n^{\log_b a-\epsilon})$，则 $T(n)=\Theta(n^{\log_b a})$。
- 若 $f(n)=\Theta(n^{\log_b a})$，则 $T(n)=\Theta(n^{\log_b a}\log n)$。
- 若 $f(n)=\Omega(n^{\log_b a+\epsilon})$, 满足正则性条件，则 $T(n)=\Theta(f(n))$。 (博客园)
3. 递归树（Recursion Tree）方法
递归树将每一层的子问题规模与调用次数可视化，将总成本分解为各层之和：
- 层 0：问题规模 n，总成本 $f(n)$。
- 层 i：有 $a^i$ 个子问题，每个规模 $n/b^i$，成本 $a^i·f(n/b^i)$。
- 深度：直到子问题规模降至常数，树高约为 $\log_b n$。
归纳求和后得出渐近形式。 (labuladong 的算法笔记)
4. 经典示例
4.1 阶乘函数
int fact(int n) {
if (n<=1) return 1;
return n * fact(n-1);
}
递归深度为 n，单次调用 O(1)，总时耗 $T(n)=T(n-1)+O(1)=O(n)$。 (开源中国)
4.2 朴素斐波那契
int fib(int n) {
if (n<2) return n;
return fib(n-1) + fib(n-2);
}
每次分成两次子调用，形成完全二叉递归树，调用总数约为 $2^n$，复杂度 $O(φ^n)$。
4.3 Merge Sort
Merge Sort 采用分治法，递归式 $T(n)=2T(n/2)+Θ(n)$。
- Master 定理第二种情形，$a=2,b=2,f(n)=Θ(n)=Θ(n^{\log_2 2})$，
- 则 $T(n)=Θ(n\log n)$。 (博客园)
5. 小结与实践建议
- 选择方法：Master 定理适用于简单分治式；递归树法适合自定义 f(n) 形式。
- 注意递归出口：避免栈深过深或无限循环。
- 结合记忆化/动态规划：对“树递归”如斐波那契进行优化，将指数级复杂度降至多项式或线性。
深入练习以上示例，掌握定理与实践相结合，助力算法面试与项目开发！
正文到此结束
- 本文标签： 递归函数 时间复杂度 算法分析
- 本文链接： https://code.itptg.com/article/79
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
