1502 : 递归的效率问题（函数专题)

斐波那契数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N）。在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1960年代起出版了《斐波纳契数列》季刊，专门刊载这方面的研究成果。



老师让小明编写程序，计算斐波那契数列的第n(0<n<30)项，小明编写的程序如下：
#include<stdio.h>
int fib(int n)

{

 if(n<=2)

    return 1;

 else

    return fib(n-1)+fib(n-2);

}
int main()

{

   int n;

   scanf("%d",&n);

   printf("%d\n",fib(n));

}


程序能够正确求解，但效率太低了。
老师为了让小明明白递归的缺点，给小明提出了新的问题：
改写以上程序，输出两行，第一行是斐波那契数列的第n项，第二行是递归求解过程中fib函数被调用的次数。

输入一个正整数n，0<n<30。

输出两行，第一行是斐波那契数列的第n项，第二行是递归求解过程中fib函数被调用的次数。

6

8
15