递归函数的运行时间

Question

int foo(int n)
{
    if(n==0)
        return 1;
    int sum = 0;
    for(int i = 0;i < n;i++)
        sum += foo(n-1);
    return sum;
}

最近在学习大O表示法。 有人可以告诉我如何使用大 O 表示法确定此递归函数的运行时间以及如何表示此函数的运行时间。

Answer 1

所以想一想如果你 运行 一个大 n 的 foo(n) 会发生什么。然后，总和包含 n 次对 foo(n-1) 的调用。在递归树的下一层我们有 foo(n-1) 并且我们再次调用 n(-1) 次 foo(n-1-1) 但是对于我们树的 n foo(n-1) 分支中的每一个.我们知道树的高度为 n，因为我们必须走到 foo(n-n)。因此，在每个递归步骤中，您将 foo 的一个实例转换为 foo(n-1) 的 O(n) 个实例。

我不确定我是否应该揭示答案，因为它看起来像是一个练习，但它似乎很明显，只需绘制递归树的几层，您就会找到答案。