上一篇提到，并非所有递推关系式都可应用支配理论。那么，递归求阶乘的算法可以用吗？

递归求阶乘算法

算法如下

int fact(int n)
{
    if(n<=1)
        return 1;
    return n*fact(n-1);
}

计算过程是 $1 \times 2 \times 3 ... \times n$，基本能直接看出来时间复杂度是 $\ O(n)$。

用主定理求解

在 CSDN 上有一篇文章^[1]https://blog.csdn.net/weixin_38233103/article/details/110592111，说用主定理求此算法的时间复杂度。来试一下，递归子问题为 $a=1$ ，输入规模每次减 1，因此 b 是一个稍微大于 1 的数字，递归过程之外的步骤时间复杂度为 $\ O(1)$，则 $d=0$，则适用于 $a=b^{d}$的情况，带入主定理公式，得复杂度为 $\ O (\log{}{n})$。

显然这个结果是错误的。

主定理的适用范围

Master theorem applies only to the divide and conquer type recurrences, like T(n) = a*T(n/b) + f(n) where a is the number of subproblems and each of these subproblem's size is 1/b of the original problem. But recurrence T(n) = T(n-1) + 2 does not technically "divide" the problem into subproblems. so master theorem does not apply here^[2]https://stackoverflow.com/questions/3224240/recurrence-relation-solving-big-o-of-tn-1.

递归求阶乘不是分治，不能用主定理求解。

正确的方法

递归求阶乘正确的递推式应该是 $T(n) = T(n-1) + 1$，即 需要的时间是 子问题的时间 加上 1 次乘法计算。设 $T(0) = 0$，将 $n=n-1, n=n-2, ..., n=n-n+1$ 依次带入递推式，两边求和，可得：

$$T(n) + T(n-1) + T(n-2) + ... + T(1) = T(n-1) + T(n-2) + ... + T(0) + \sum_{1}^{n} 1$$

因此：

$$T(n) = n + T(0)$$

所以复杂度是 $\ O(n)$