深入浅出：递归函数的时间复杂度分析与示例

1. 什么是递归及其时间复杂度

递归（Recursion）是函数调用自身来解决问题的编程技术。时间复杂度分析需考虑每次调用的额外工作量、递归深度以及分支数目。

“递归结束的条件”称为递归出口，若出口设置不当可能导致无限循环或栈溢出。 (Hexo)

2. Master 定理：分治算法的利器

对于形如：

T(n) = a · T(n/b) + f(n)

的递归式，Master 定理可直接给出三种情形的渐近解：

1. 若 f(n)=O(n^{\log_b a-\epsilon})，则 T(n)=\Theta(n^{\log_b a})。
2. 若 f(n)=\Theta(n^{\log_b a})，则 T(n)=\Theta(n^{\log_b a}\log n)。
3. 若 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) 形式。
• 注意递归出口：避免栈深过深或无限循环。
• 结合记忆化/动态规划：对“树递归”如斐波那契进行优化，将指数级复杂度降至多项式或线性。

深入练习以上示例，掌握定理与实践相结合，助力算法面试与项目开发！