CODEWITHSUNDEEP
c++recursion
user2661167
user2661167

Reputation: 491

Recursion counter inside a C++ function

Doing an assignment on recursive functions at the moment. Was asked to do a Fibonacci program and did so with out much issue. But I'm need to make a counter for it, and here is where I'm getting stuck.

I've got this function

int fibonacci(int n)
{
    if( n == 0 )
    {
        //my fibonacci code 
    }
    else if( n == 1 )
    {
        //my fibonacci code
    }
    else 
    { 
        //my fibonacci code
    }
}

So how to I add a counter to this? Ever time I add a counter it returns the wrong number.

Edit Just to clarify, my function works fine generating the Fibonacci numbers. I just wanted to add a counter inside the function so I can see how many times it is being called every time I want it to generate a Fibonacci number.

I have since tried one of the methods below where I initialise a counter in the main function then increment it in the recursion but don't know if the number is correct. For example it is saying that I'm calling the function 609 times if my Fibonacci number is 610, is that correct?

Upvotes: 4

Views: 19088

Answers (4)

Moises Rojo
Moises Rojo

Reputation: 381

Using struct could be the answer.

struct factorial
{
  factorial() : counter(0)
  {}

  uint64_t foo(uint64_t x) {
    ++counter;

    if(x < 2)
      return 1;
    else
      return x * foo(x - 1);
  }

  template <class T>
  T operator()(const T& x) {
    return foo(x);
  }

  uint64_t counter;
} factorial;

In this case, foo is the factorial function. but doesn't have that name, because the usage of the struct will be.

// output and calls
struct factorial foo;
std::cout << foo(5) << "\n";
std::cout << foo.counter << "\n";

// output
std::cout << factorial(5) << "\n";

Upvotes: 0

mvw
mvw

Reputation: 5105

Complete the code first. I give you the recursion equations:

fib(0) = *deleted*
fib(1) = *deleted*
fib(n) = *deleted*

Your counter (which you should still specify in your question) can be usually implemented by a global variable defined outside the function but be changed within the function.

Referring to the question's edit:

Your number is not good. To not spoil your task more, I give you the answer in Erlang, so you still have some work left to figure out how to get it right in your C++ task. :-)

-module(fib).

-export([f/1]).

%% returns a tupel { fibonacci value, number function calls }
f(0) -> {0, 1};
f(1) -> {1, 1};
f(X) -> 
    {F1, C1} = f(X - 1),  %% decompose tuple
    {F2, C2} = f(X - 2),
    {F1 + F2, C1 + C2}.  %% return value

Running this from a shell gives:

Eshell V5.10.1  (abort with ^G)
1> c("q:/doc/erlang/fib", [{outdir, "q:/doc/erlang/"}]).
{ok,fib}
2> fib:f(0).
{0,1}
3> fib:f(1).
{1,1}
4> fib:f(2).
{1,2}
5> fib:f(3).
{2,3}
6> fib:f(4).
{3,5}
7> fib:f(5).
{5,8}
8> fib:f(6).
{8,13}
9> fib:f(7).
{13,21}
10> fib:f(15).
{610,987}
11>

Thus I get 987 function calls to get at the F(15) = 610 value.

The interesting bit here is, in the comments we talked about the proper start conditions for the Fibonacci recursion F (the situation is similar to differential equations, a different start point gets you on a different trajectory / solution).

I got it wrong with F(0) = 1 and F(1) = 1, while @WhozCraig correctly pointed out it should be F(0) = 0 and F(1) = 1.

If you look at the Erlang code above you see that the calculation of the series which yields the number of function calls is a Fibonacci type one as well (adding the last two members of the series), but that one is the one with the start values 1 and 1! :-)

Upvotes: 0

codeling
codeling

Reputation: 11369

I'm guessing you just need the count for demonstration purposes, right? Counting the calls should be easily achievable by passing in a counter variable by reference, and increasing it once at the beginning of each call, like so:

#include <iostream>

// ...

int fibonacci(int n, int &count)
{
    ++count;
    // other code ...

    // and every time you call fibonacci recursively,
    // simply pass in the same reference, like so:
    if (...) {
        fibonacci (new_n, count);
    }
}

int main(int argc, char** argv)
{
    // call it with an int variable initialized to 0:
    int fibCnt = 0;
    fibonacci(10, fibCnt);
    std::cout << "Function was called "<<fibCnt<<" times"<<std::endl;
}

Upvotes: 4

Walter
Walter

Reputation: 45424

You don't need any counters. Your code is already almost there

int fibonacci(int n)
{
    if( n == 0 )
    {
        return f_0
    }
    else if( n == 1 )
    {
        return f_1
    }
    else 
    { 
        return f_n using recursion
    }
}

As the Fibonacci numbers are defined via recursion, the last case is obvious. The other two are needed only to close the recursion relations, i.e. to avoid the last case to result in an infinite loop.

Upvotes: 1

Related Questions