分析递归算法

递归算法的分析取决于我们使用的递归类型。如果是线性递归，复杂度就会不同；如果是二进制递归，复杂度就会不同。因此，我们没有递归算法的通用复杂度。我们必须根据具体情况进行分析。在这里，我们将分析阶乘数列。首先，让我们关注阶乘部分。如果我们还记得本节的内容，阶乘递归算法是这样的：

function factorial(int $n): int {
    if ($n == 0)
        return 1;

    return $n * factorial($n - 1);
}

假设计算阶乘 ($n) 需要 T(n)。我们将重点讨论如何用大 O 符号来使用这个 T(n)。每次调用阶乘函数时，我们都需要经过一些步骤：

  1. 每次，我们都在检查基本情况。

  2. 然后，我们在每个循环中调用阶乘 ($n-1)。

  3. 我们在每个循环中与 $n 进行乘法运算。

  4. 然后，我们返回结果。

现在，如果我们使用 T(n) 来表示，那么我们可以说：

T(n) = a when n = 0
T(n) = T(n-1) + b when n > 0

这里，a 和 b 都是一些常数。现在，让我们生成 a 和 b 与 n 之间的关系：

T(0) = a
T(1) = T(0) + b = a + b
T(2) = T(1) + b = a + b + b = a + 2b
T(3) = T(2) + b = a + 2b + b = a + 3b
T(4) = T(3) + b = a + 3b + b = a + 4b

我们可以看到这里正在出现一种模式。因此，我们可以确定：

T(n) = a + (n) b

或者，我们也可以简单地说 \$T(n) = O(n)\$。

因此，阶乘递归的线性复杂度为 \$O(n)\$。

带递归的斐波那契数列的复杂度约为 \$O(2^n)\$。由于我们必须同时考虑大 O 符号的下界和上界，因此计算非常复杂。在接下来的章节中，我们还将分析二进制递归，如二进制搜索和合并排序。在这些章节中，我们将更多地关注递归分析。