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

时间限制:1 Sec 内存限制:128 MiB
提交:248 答案正确:206

提交 状态 讨论区

题目描述

斐波那契数列,指的是这样一个数列: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

提示

数列第6项是8,fib()函数被调用15次。

来源