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

假设我有下面的递归函数，它返回第n个斐波那契数：

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

我将如何编写一段代码来返回此函数所产生的递归调用的总数量？ 我正在考虑在递归调用之前引入一个计数参数，如fib(int n, int count = 0)或fib的静态变量static int count = 0和递增计数。 这两种方法我都没有成功，因为我不能回count 。 有没有办法在不修改原始函数的情况下获得递归调用的总数？

---

你可以通过归纳计算出计算F(n)的递归调用次数为2 * F(n) - 1 （对于n <= 2的基本情况，它是1）。 试着写感应步骤，如果你不能，我会稍后更新我的答案和证明。

所以实际上不需要编写递归算法。 还有O(log(n))算法来计算基于矩阵求幂的第n个斐波那契数。

因此，通过一些数学运算，您可以使用O(log(n))算法来查找递归调用的数量。 但是如果你将继续修改你的函数，你会发现这约为O(1.6^n)

---

无需修改功能？ 使用代理

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

---

您可以使用引用变量来跟踪函数被调用的时间。

你为什么不尝试这样的事情：

#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/80681.html

上一篇: Writing a program to count the number of recursive calls

下一篇: Recursion binomial coefficient