本文共 981 字，大约阅读时间需要 3 分钟。

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39

思路：这个题太简单了，思路不说了

1. 递归方法：

class Solution {public:    int Fibonacci(int n) {        if (n == 0 ){            return  0;        }        else if(n==1||n==2){            return  1;        }        else{            return Fibonacci(n - 1) + Fibonacci(n - 2);        }    }};

运行结果：运行时间： 750 ms 占用内存：8568K 状态：答案正确

2. 换代方法：

class Solution {public:    int Fibonacci(int n) {        int fib[40]={
  0,1};        int i=2;        for(;i<=n;++i){            fib[i]=fib[i-1]+fib[i-2];        }        return fib[n];    }};

运行结果： 运行时间： <1 ms 占用内存：8568K 状态：答案正确

总结：刚开始对递归的理解不够深刻，跑出来的结果吓一跳，真的太慢了！！！

原因： 测试用例里肯定准备着一个超大的n来让Stack Overflow，为什么会溢出？因为重复计算，而且重复的情况还很严重，举个小点的例子，n=4，看看程序怎么跑的： Fibonacci(4) = Fibonacci(3) + Fibonacci(2); = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0); = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0); 由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时f(1)就重复计算了3次之多。

转载地址：http://cimii.baihongyu.com/