CODEWITHSUNDEEP
algorithmrecursion
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Writing a program to count the number of recursive calls

Suppose I have the following recursive function, that returns the nth fibonacci number:

private int fib(int n) {
    if(n == 1) return 0;
    if(n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

How would I write a piece of code to return the total number of recursive calls made by this function ? I was thinking of introducing a count parameter as in fib(int n, int count = 0) or a static variable inside fib as static int count = 0 and increment count right before the recursive call. I had no success with either of these two approaches as I couldn't return count. Is there a way to get the total number of recursive calls without modifying the original function ?

Upvotes: 1

Views: 1835

Answers (3)

I wrestled a bear once.
I wrestled a bear once.

Reputation: 23379

Without modifying the function? Use a proxy:

Foo foo = (Foo) DebugProxy.newInstance(new FooImpl());
foo.bar(null);

Upvotes: 0

user321156
user321156

Reputation: 1

You can use a reference variable to keep track of the times the function is called.

Why don't you try something like this:

#include <iostream>

using namespace std;

 int fib(int n,int& count) {
     count++;
    if(n == 1) return 0;
    if(n == 2) return 1;
    return fib(n - 1,count) + fib(n - 2,count);
}
int main()
{
   int nth=7;
   int count=0;
   int num=fib(nth,count);

   cout<<nth<<"th fibonacci sequence is "<<num<<" function calls: "<<count<<"recursive calls:"<<count-1<<endl;
   return 0;
}

Upvotes: 0

Salvador Dali
Salvador Dali

Reputation: 222511

You can calculate by induction that the number of recursion calls to calculate F(n) is 2 * F(n) - 1 (for the basic case where n <= 2 it is 1). Try to write induction steps, if you will not be able, I will update my answer with a proof later.

So actually there is no need to write a recursive algorithm. Also there is O(log(n)) algorithm to calculate n-th fibonacci number based on matrix exponentiation.

enter image description here

So with some math, you can end up with an O(log(n)) algorithm to find the number of recursive calls. But if you will continue modifying your function, you will find this in approximately O(1.6^n)

Upvotes: 1

Related Questions