4 斐波那契数列
作者: Turbo时间限制: 1S章节: 递归
问题描述 :
斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次类推下去，你会发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。
递归思想：一个数等于前两个数的和。(这并不是废话，这是执行思路)
首先分析数列的递归表达式：
如果调用f(2)，则可知，需要计算f(1)+f(0)=1+0
因此，可以知道，f(2)=1，递归函数f(n)总共被调用3次，其中使用实参为2、为1、为0各调用一次
如果计算f(4)，则可知f(4)=f(3)+f(2)， 而f(3)=f(2)+f(1)， 继续调用，可知f(2)=f(1)+f(0)
从以上分析可知：
计算f(3)，需要调用5次f(n)
计算f(4)，需要调用9次f(n)
请使用递归方式实现本程序。
输入说明 :
输入一个整数n
输出说明 :
输出f(n)的值，以及总共需要调用几次f函数，中间以空格分隔。
输入范例 :
4
输出范例 :
3 9
#include
using namespace std;
int total = 0;
int circle(int n) {
total++;
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else if(n>1)
{
return circle(n - 1)+circle(n - 2);
}
}
int main() {
int x = 0;
cin >> x;
int y = circle(x);
cout 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
