三种方法求斐波那契数列的第n项--java

斐波那契数列的定义

上图是百度对于斐波那契数列的定义。

总的来说：这个数列从第3项开始，每一项都等于前两项之和。

代码实现：

1、递归

相信大家对于递归都不陌生了，递归就是一个程序调用自身的编程技巧。

这里第一种方法就采用递归的形式来解决这个问题。

下面上代码：

程序运行截图：

但是用递归方法解决这个问题存在一个问题就是当你要求的数字较大时，函数调用可能会造成栈溢出的错误。

就是这样的：

首先这个光标不停的闪烁，说明电脑没有偷懒一直在计算，但是短时间没计算出来。

2、循环

前两种方法都有可能造成栈溢出的问题，接下来第三种方法就大概率不会了。

3、迭代

思想：

每一次执行到f(n-1)和f(n-2)时都要重新计算一遍，还要开辟新的空间来保存它们，比较浪费空间，可以优化为：开辟一个缓存区，存放计算过的每一个值，下一次用到时直接从缓存区查找，找不到则再计算，如此，可以减少空间上的浪费。