تعداد گامهای فیبوناتتچی به صورت بازگشتی

[kamran_14]

سلام
آیا رابطه ای وجود دارد که بتونیم تعداد دفعاتی را که تابع فیبوناتچی( که به صورت بازگشتی نوشته شده) فراخوانی می شود را محاسبه کنیم؟



float fib(int a)
{
if (a==1 || a==2)
return 1;
else
return fib(a-1)+fib(a-2);
}

[simul8or]

سلام
آیا رابطه ای وجود دارد که بتونیم تعداد دفعاتی را که تابع فیبوناتچی( که به صورت بازگشتی نوشته شده) فراخوانی می شود را محاسبه کنیم؟



float fib(int a)
{
if (a==1 || a==2)
return 1;
else
return fib(a-1)+fib(a-2);
}

رابطه را نمیدانم ولی اگر تعداد دفعات فراخوانی را نیاز داشته باشید به صورت زیر شمرده میشود، اگر اشتباه نکنم:


#include <iostream>
#include <cstdlib>

using namespace std;
int count=0;
float fib(int a)
{
count++;
if (a==1 || a==2)
return 1;
else
return fib(a-1)+fib(a-2);
}

int main()
{
cout<<fib(10)<<endl;
cout<<count-1;

system("pause");
return 0;
}