-1

I know I need a program counter for this, I need to keep track of each recursive call or steps, this is easy to do in a for loop, however hard for a recursive program. I am stuck as to how I could count all the recursive steps. So far this is what I have. I was also thinking of making my method void but with int I could at least try and return counter based on the final steps, but it is not working.

int fibRec( int x, int counter )
{  
    if (x == 0)
        return  0;
    else if (x == 1)
        return 1;
    else
    {
        counter++;
        return fibRec((x - 1) + (x - 2), counter);
    }
}
Jam1
  • 629
  • 12
  • 25

3 Answers3

2

this is easy to do in a for loop, however hard for a recursive program

Sorry, you are wrong -- it is trivial to add counters or such for a recursive program in C++.

a) Note that no global is needed.
b) No extra method parameter is needed.

As usual, the C++ solution is to create a class

The non-static recursion method as part of a class will always have the this pointer, and thus access to any part of the class, including any number of added counters and reports or methods you might need.

Here is one possible approach:

class FibRec
{
public:
   FibRec() : counter(0) {
      std::cout << "FibRec ctor " << counter << std::endl;
   };

   ~FibRec() { // output final value with dtor
      std::cout << "FibRec dtor " << counter << std::endl;
   };

   int exec( int x )
      {
         if (x == 0)       return  0;
         else if (x == 1)  return 1;
         else
         {
            counter++;
            // dbg: std::cout << counter << "  " <<  x << std::endl;

            return (exec(x - 1) + exec(x - 2)); 
            // note -- Fibonacci fix?
         }
      }
private:
   int counter;
};


int t407(void)
{
   FibRec f;   // class instance
   f.exec(5);  // invoke recursive method

   return(0);
}

Note: The default stack size on ubuntu 15.10, using g++, is 8 Mbytes. That is a LOT of recursion.

Unfortunately, your code has a mistake - it 'adds' and grows to overflow very quickly. My code shows overflow when counter is 272,261. You'll need to fix the code.

I'm guessing that this code is supposed to be fibonacci, which is the sum of two intermediate values. Not what you have coded.

You might achive what you want by changing your code from:

return fibRec((x - 1) + (x - 2), counter);

to:

return (fibRec(x - 1, counter) + fibRec(x - 2, counter));

Good luck.

2785528
  • 5,438
  • 2
  • 18
  • 20
  • That is the essence of the program, to show how much steps to calculate the nth Fibonnaci number. I got 2178278 steps for the first 30 Fibonacci sequence based on my algorithm. – Jam1 May 03 '16 at 18:17
  • Also your method looks pretty advanced, I am just starting out, things that might be simple for you are hard for me. But I like your input and I will take what you say in the future. I ended up declaring `counter` as a global variable for `main` and just increment in the `fib()` method, this way I get to access `counter` for output purposes in `main`. Thanks for your input. – Jam1 May 03 '16 at 18:27
1

You'll want to pass counter in as a reference:

int fibRec( int x, int &counter )

That way the caller's local variable that was passed in is updated. Also, you'll probably want to consider incrementing counter for the base cases (0 and 1) since they technically are steps too.

Michael Albers
  • 3,721
  • 3
  • 21
  • 32
  • Worth noting the downside of this: Unless the compiler's doing some really cool stuff, this doubles or triples the memory used by every call. You'll run out of storage faster. – user4581301 May 03 '16 at 00:12
  • Thanks did that for incrementing the base cases, however I ended up declaring counter as a global for `main` method and just used it in the recursive fibonnaci method. That way I was able to print the counter value in main once the `fib()` finished. Thanks again. – Jam1 May 03 '16 at 18:20
0

Either you can pass a variable as a reference

void fibRec( int x, int &counter )

or you can declare a global variable counter like the code below

int counter = 0;
int fibRec( int x )
{  
    if (x == 0)
        return  0;
    else if (x == 1)
        return 1;
    else
    {
        counter++;
        return fibRec((x - 1) + (x - 2));
    }
}
Laschet Jain
  • 734
  • 1
  • 8
  • 24
  • Recommend making `counter` `static thread_local int counter = 0;` More here: http://en.cppreference.com/w/cpp/language/storage_duration and here http://stackoverflow.com/questions/11983875/what-does-the-thread-local-mean-in-c11 – user4581301 May 03 '16 at 00:17