递归调用和普通调用的区别

Question

设函数f();

void f(int n)
{
  if(n<=1)
    return;
  f(n-1);
  f(n-1);
}

关于这段代码我有 2 个主要问题：

1. 递归调用的总数是多少？
2. 总调用次数是多少？

还有这段代码的时间复杂度是多少？

基本上，我想了解调用和递归调用之间的区别以及总调用是否还包括递归调用。

Answer 1

我会专注于你的术语问题

Basically, I want to understand difference between calls and recursive calls and whether total calls also include the recursive calls.

剩下的就是数数了，你一定可以自己做。

递归调用是来自同一函数的调用。所以，例如你的函数 f() 包含两个递归调用，都是 f(n-1).

如果有人调用 f(4)，那么这是一个非递归调用（不是来自 f() 内部），并且通过 f(n-1) 会导致大量递归调用，其中 f() 调用自身。

所以：

• 总调用 = 调用，计算非递归和递归调用。
• 递归调用是来自内部的调用 f()。