CODEWITHSUNDEEP
c++functionrecursion
Ben
Ben

Reputation: 563

A Recursion function in C++

If I have this recursive function:

int mystery(int n) {

if ( n == 0 || n == 1 ||  n ==  2) return  n ;
 return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

I am working with finding mystery(20).

How can I find out how many addition operations are carried out when calculating the function and how many invocations of mystery() there are in order to calculate mystery(20)?

I tried adding some cout statements like:

int mystery(int n) {
    if ( n == 0 || n == 1 ||  n ==  2) {
      cout << n << endl; 
      return  n ;
    }
        cout << n << endl;
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

But I couldn't really make sense of it since there were over a thousand numbers outputted. And I don't believe those cout statements do much in the way of telling me how many addition operations are carried out and how many invocations of mystery() there are in order to calculate mystery(20)?

Thanks for any and all help!

Upvotes: 1

Views: 1649

Answers (6)

Omnifarious
Omnifarious

Reputation: 56088

This is possible to figure out with math. But if you wanted to measure it empirically, you could use a static counter in the function. This logic is easy to extend to counting the number of additions as well.

int mystery(int n) {
    static int invocations = 1;

    cout << "mystery has been invoked " << invocations++ << " times.\n";
    if ( n == 0 || n == 1 ||  n ==  2) {
      return  n ;
    }
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

You could also use a global variable. I don't like either of those solutions though. They make multi-threading hard, and they violate some important design principles. As a one-off to answer this question and then remove from your code they're fine, but what I would do if I wanted this as a permanent feature is this:

#include <iostream>

class counted_mystery {
   public:
    counted_mystery() : invocations_(0), additions_(0) { }

    unsigned int getInvocations() const { return invocations_; }
    void resetInvocations(unsigned int newval = 0) { invocations_ = newval; }

    unsigned int getAdditions() const { return additions_; }
    void resetAdditions(unsigned int newval = 0) { additions_ = newval; }

    operator ()(int n) {
        ++invocations_;
        counted_mystery &mystery = *this;

        if ( n == 0 || n == 1 ||  n ==  2) {
          return  n ;
        }
        // The code is about to perform two additions.
        additions_ += 2;
        return (mystery(n-1) + mystery(n-2) + mystery(n-3));
    }

   private:
    unsigned int count_, additions_;
};

int main(int argc, char *argv[])
{
    using ::std::cout;

    counted_mystery mystery;
    mystery(20);
    cout << "mystery was called " << mystery.getCount() << " times for n == 20\n";
    return 0;
};

Figuring this out with math is an interesting problem, but likely not too hard. I think it will turn out to be exponential.

BTW, don't use endl unless that's what you mean to use. It's very slow since it forces a buffer flush whenever you use it. Use '\n'.

Upvotes: 2

Keith
Keith

Reputation: 6834

Another option is to make this is method of a class which would allow use of a member variable rather than a global, and at the same time keeps the int mystery(int) interface clean.

Upvotes: 1

BenjaminB
BenjaminB

Reputation: 1869

The easiest way to do is to increment a global (or static global) variable.

Something like to get the number of mystery call:

int nb_of_invok = 0;
int mystery(int n)
{
  nb_of_invok++;
  ...your code here...
}

And this to get the number of additions:

int nb_of_invok = 0;
int nb_of_add = 0;
int mystery(int n)
{
  nb_of_invok++;
  if(...)return n;
  nb_of_add++;
  return(...);
}

Upvotes: 4

colechristensen
colechristensen

Reputation: 472

Use (and increment) a global variable. http://www.cplusplus.com/doc/tutorial/variables/

I would type an example but I've got a hand injury.

Upvotes: 0

jonsca
jonsca

Reputation: 10381

Declare two different static int variables to keep track of number of times invoked and number of addition operations.

Upvotes: 0

Mike Park
Mike Park

Reputation: 10941

If I'm understanding you correctly... you can use a static counter variable and increment that every time you call the method. Alternatively, you can pass around a reference to the counter and just increment that.

Upvotes: 2

Related Questions