Difference between recursive calls and normal calls

Question

Let there be a function f();

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

I have 2 major questions regarding this code:

1. What is the total number of recursive calls?
2. What is the total number of calls?

and also What is the time complexity of this code?

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

Answer 1

I'll concentrate on your terminology question

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

Then the rest is counting, which you can surely do yourself.

A recursive call is a call that comes from the same function. So, e.g. your function f() contains two recursive calls, both being f(n-1).

If someone calls f(4), then that is one non-recursive call (not coming from inside f()), and, via f(n-1) it causes a lot of recursive calls, where f() calls itself.

So:

• Total calls = calls, counts both non-recursive as well as recursive ones.
• Recursive calls are those that come from inside f().