How can I find number of times a recursive function calls itself?

Question

Consider the following recursive C function.

 void get (int n) { 
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
    }

If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main 0 ?

That will depend on the value of the (global?) variable `l`, I think... — glglgl, Feb 12 '15 at 06:38
I recommend putting in a counter (a static variable) that increments every time `get()` is entered. — Gabe, Feb 12 '15 at 06:39
@glglgl: I'm guessing that's a typo -- `l` should be `1` (ell should be one) — Gabe, Feb 12 '15 at 06:39
@Gabe I would have up-voted it if it was a answer.. Very good suggestion — Gopi, Feb 12 '15 at 06:40
I would imagine that `l` (`L`) is a typo and the author meant to write `1` (one). — Spencer D, Feb 12 '15 at 06:40
I'm not sure what anyone else thinks, but this kind of sounds like a homework question. — Spencer D, Feb 12 '15 at 06:43
just put some static variable or global variable increment it in get function and print. for get(6) if l=1 then 25. — Prashant, Feb 12 '15 at 06:43
Exam in the class: irrelevant C knowledge. A good c programming class would rather reach you to avoid recursion whenever possible. This is kind of like a driving class teaching you the best ways to crash your car or how to drive really slow on the free-way. "It is good to know". No, not really. Why would you want to drive slow with the risk of crashing, when you could drive bother faster and safer? — Lundin, Feb 08 '17 at 07:51
@Lundin Well it's basically to test knowledge of students "if they understand recursion or not", Its like testing them for basics so that higher things could be taught to them. — Rishi, Feb 08 '17 at 12:37
@RishiPrakash No it's all about teaching them bad practice, so that they end up using it in real-world applications later on, turning the applications into slow, buggy crap. The uses for recursion are so very limited that the average professional programmer never encounters a valid use-case for it. The only valid, but extremely narrow case I know of myself, is when you are picky about optimizing a BST for storage size, by implementing the BST with nodes that don't have a parent pointer. Yet plenty of programming classes forces beginners to study recursion, which is outright harmful. — Lundin, Feb 08 '17 at 13:55
@Lundin experience speaks, I agree because whatever you would be saying must be saying with all the experience and time you have spent with real world programs. — Rishi, Feb 09 '17 at 11:43

Gabe · Accepted Answer · 2015-02-12T07:22:10.457

5

To figure out how many times your function gets called, increment a static counter every time the function is entered and the print out the value after the call. For instance:

int counter;
void get (int n) { 
    ++counter; /* increment counter before first return */
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
}

int main()
{
    counter = 0; /* reset counter before each use */
    get(6);
    printf("get() was called %d times\n", counter);
}

edited Feb 12 '15 at 07:22

answered Feb 12 '15 at 06:42

Gabe

84,912
12
139
238

1

FWIW, There's no need to initialize `counter` in `main()`. Global variable in C [are guaranteed to be initialized to zero](http://stackoverflow.com/q/16015656/119527). – Jonathon Reinhart Feb 12 '15 at 07:06
2

@JonathonReinhart: You are absolutely right, but I wanted to make the code so it could be reused; that is, you could call it in a loop or copy/paste it to see how many times the function gets called with different input parameters. – Gabe Feb 12 '15 at 07:21
@JonathonReinhart Writing code that relies on implicit zero-initialization of objects with static storage duration is very bad practice. Dangerous, unmaintainable, confusing. – Lundin Feb 08 '17 at 07:42
@Lund in Citation, please? I don't see how it's any different than not `memset`-ing a buffer returned by `calloc` to all-zeroes. – Jonathon Reinhart Feb 08 '17 at 10:33
@JonathonReinhart I can't cite common sense. Suppose for example that you have a global variable and someone maintaining the code finds this ugly and unnecessary, so they move it to local scope, which is a reasonable thing to do. This maintenance exposed a bug written by the original programmer. Which could have easily been avoided by writing `int counter=0;`. – Lundin Feb 08 '17 at 10:55
I'm afraid we'll have to agree to disagree that this is a "bug" by the original author. There are multiple problems with your scenario: 1) He can't move this variable to a local scope because it's referenced by another function. When he goes to compile, he's reminded that it is a global, and because he knows the language, he knows that it was zero-initialized. 2) Because he's a good programmer, he has compiler warnings enabled and sees that his now-local variable is uninitialized. – Jonathon Reinhart Feb 08 '17 at 11:07

Jonathon Reinhart · Answer 2 · 2015-02-12T07:04:23.373

Considering this is certainly an academic exercise, it may behoove you to understand how the recursion is working.

We can modify your code to print out a call tree, showing each invocation:

#include <stdio.h>

void get(int n, int depth)
{ 
    static int call = 1;
    printf("%3d: %*sget(%d)\n", call++, 2*depth, "", n); 
    if (n<1)
        return; 
    get(n-1, depth+1); 
    get(n-3, depth+1); 
}

int main(void)
{
    get(6, 0);
    return 0;
}

Output:

  1: get(6)
  2:   get(5)
  3:     get(4)
  4:       get(3)
  5:         get(2)
  6:           get(1)
  7:             get(0)
  8:             get(-2)
  9:           get(-1)
 10:         get(0)
 11:       get(1)
 12:         get(0)
 13:         get(-2)
 14:     get(2)
 15:       get(1)
 16:         get(0)
 17:         get(-2)
 18:       get(-1)
 19:   get(3)
 20:     get(2)
 21:       get(1)
 22:         get(0)
 23:         get(-2)
 24:       get(-1)
 25:     get(0)

Note that I am assuming your assignment states if (n<1) ("one"), not if (n<l) ("ell"). Also, notice that I added a depth parameter. This allowed me to indent each call appropriately.

score 2 · Answer 3 · edited Jul 09 '18 at 18:45

2

We can make a recurrence relation for above function as:

T(n) = T(n-1)  +  T(n-3) + 2

T(n)=1 for n<=0

I've added 2 in the equation since we are calling the recursive function twice.

Start by by substituting from n=1 at n=6 you will get ans as 25

edited Jul 09 '18 at 18:45

mickl

48,568
9
60
89

answered Jul 09 '18 at 18:25

Sahil

41
1
7

How can I find number of times a recursive function calls itself?

3 Answers3