ein Programm schreiben, um die Anzahl der rekursiven Aufrufe zählen

Question

Angenommen, ich habe die folgende rekursive Funktion, die die n-te Fibonacci-Zahl zurückgibt:

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

Wie würde ich ein Stück Code schreiben die Gesamtzahl der rekursiven zurückzukehren Anrufe von dieser Funktion gemacht? Ich dachte über die Einführung eines Zählparameters wie in fib(int n, int count = 0) oder einer statischen Variablen innerhalb als static int count = 0 und Inkrementierung direkt vor dem rekursiven Aufruf. Ich hatte keinen Erfolg mit einem dieser beiden Ansätze, da ich count nicht zurückgeben konnte. Gibt es eine Möglichkeit, die Gesamtzahl der rekursiven Aufrufe zu erhalten, ohne die ursprüngliche Funktion zu ändern?

Answer 1

ohne die Funktion zu ändern? verwenden einen 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); 

Answer 2

Sie durch Induktion berechnen kann, dass die Anzahl der Rekursion zu berechnen ruft F(n) ist 2 * F(n) - 1 (für den Fall, in dem Grund n <= 2 es ist 1). Versuchen Sie Induktionsschritte zu schreiben, wenn Sie nicht in der Lage sind, werde ich meine Antwort später mit einem Beweis aktualisieren.

Also eigentlich ist es nicht notwendig, einen rekursiven Algorithmus zu schreiben. Auch gibt es O(log(n)) Algorithmus zur Berechnung der n-ten Fibonacci-Zahl basierend auf Matrix Exponentiation.

So mit etwas Mathematik, können Sie sich mit einem O(log(n)) Algorithmus Ende die Anzahl der rekursiven Aufrufe zu finden. Wenn Sie jedoch fortfahren, Ihre Funktion zu ändern, finden Sie diese in ungefähr O(1.6^n)

Answer 3

Sie können eine Referenzvariable verwenden, um die Zeiten zu verfolgen, zu denen die Funktion aufgerufen wird.

Warum Sie nicht so etwas wie dies versuchen:

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