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 ?

---

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.

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)

---

without modifying the function? use a proxy..

http://tutorials.jenkov.com/java-reflection/dynamic-proxies.html#proxy

http://java.sun.com/j2se/1.4.2/docs/guide/reflection/proxy.html#examples

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

---

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;
}

链接地址: http://www.djcxy.com/p/80682.html

上一篇: 在Haskell中的尾递归

下一篇: 编写一个程序来计算递归调用的数量