CODEWITHSUNDEEP
c++pointersrecursioncounterfunction-pointers
Arthur Johnson
Arthur Johnson

Reputation: 21

Number of additions in a recursive function without using global variables in c++

I have to implement a counter that counts the number of additions in this recursive function, but i am not allowed to use global variables. Do you know how to do that? For example if the function has to call itself free times then my counter has to be put on three at the end of the function just before the return. 

long lindh(unsigned int n) {

  long lin = 0;
  if (n == 1 || n == 2) {
    lin = 1;
  } else {
    lin = 1 * lindh(n - 1) + 3 * lindh(n - 2);
  }

  return lin;
}

int main() {
  long b = 0;
  b = lindh(24);

  cout << "lindhauer " << b << endl;

  return 0;
}

Upvotes: 0

Views: 627

Answers (2)

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

You can define an overloaded lindh function that takes two arguments. The overloaded function takes two parameters, while the version called from main is the "base" function that just delegates to the overloaded function.

In addition, since you need to return both a lin value and count, you can return a std::pair<long, int> to denote the lin value and count. This eliminates the need for a global variable,

Here is an example:

#include <utility>
#include <iostream>


long lindh(unsigned int n, int &count) 
{
  long lin = 0;
  if (n == 1 || n == 2) {
    lin = 1;
  } else {
    ++count;
    lin = 1 * lindh(n - 1, count) + 3 * lindh(n - 2, count);
  }
  return lin;
}

std::pair<long,int> lindh(unsigned int n) 
{  
   int count = 0;
   return {lindh(n, count), count};
} 

int main() 
{
   auto b = lindh(24);
   std::cout << "lindhauer = " << b.first << "\ncount = " << b.second << std::endl;
}

Live Example

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49803

You can change the function signature to be:

long lindh(unsigned int n, int &count)

Pass it the variable you want the count to end up in, in both the initial call and every recursive one. Increment count in the appropriate places.

Upvotes: 3

Related Questions