#includeint Fib(int n){if (n<=2){return 1;}else{return Fib(n - 1)+Fib(n - 2);}}int main(){int n = 0;scanf("%d", &n);int ret=Fib(n);printf("%d", ret);return 0;}
查数据得:
第五项斐波那契数是:5。
运行结果:
当我们n输⼊为50的时候,需要很⻓时间才能算出结果,这个计算所花费的时间,是我们很难接受的,这也说明递归的写法是非常低效的,那是为什么呢?
其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计算,而且递归层次越深,冗余计算就会越多。
进行测试:
#include int count = 0;int Fib(int n){ if(n == 3) count++;//统计第3个斐波那契数被计算的次数 if(n<=2) return 1; else return Fib(n-1)+Fib(n-2);}int main(){ int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret);printf("\ncount = %d\n", count); return 0;}
这里我们看到了,在计算第40个斐波那契数的时候,使用递归方式,第3个斐波那契数就被重复计算了39088169次,这些计算是非常冗余的。所以斐波那契数的计算,使用递归是非常不明智的,我们就得想迭代的方式解决。
#includeint Fib(int n){int a = 1, b = 1, c = 1;while (n > 2){a = b;b = c;c = a + b;n--;}return c;}int main(){int n = 0;scanf("%d", &n);int numb = Fib(n);printf("%d", numb);}
这个结果的出现花费的时间非常快,
这个第50个斐波那契数太大了,一个整型放不下,所以是负滴。
青蛙跳台阶问题,也是属于求n个斐波那契数列。有时候,递归虽好,但是也会引⼊⼀些问题,所以我们⼀定不要迷恋递归,恰到好处就好。
欧耶!!!!我学会啦!!!!!!