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:

What is the total number of recursive calls?
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.

Does this answer your question? [Determining complexity for recursive functions (Big O notation)](https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation) — dahiya_boy, May 03 '21 at 07:28
Try drawing a recursion tree and/or using the master theorem — Abhinav Mathur, May 03 '21 at 09:44

score 1 · Accepted Answer · answered May 03 '21 at 11:05

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().

Difference between recursive calls and normal calls

1 Answers1