链接：https://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3
来源：牛客网
这个题可以说是迭代（Iteration） VS 递归（Recursion），
f(n) = f(n-1) + f(n-2)，第一眼看就是递归啊，简直完美的递归环境，递归肯定很爽，这样想着关键代码两三行就搞定了，注意这题的n是从0开始的：
|
1
2
|
if(n<=1) return n;
else return Fibonacci(n-1)+Fibonacci(n-2);
|
然而并没有什么用，测试用例里肯定准备着一个超大的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://www.cnblogs.com/cs-lcy/p/7258685.html
